根和叶

消息队列、文件系统、网络路由等场景经常需要处理路由信息，一般都是由路径节点名和分隔符做成,比如:

  • /usr/lib/apache2/modules/httpd.exp
  • /topic/who/am/i

实际上这种结构，可以看作是从树的根节点到某个叶子节点的完整路径，也就是说这种结构的集合是一棵树 然后加上路由信息常见使用场景都涉及到匹配，所以大多数情况，这里数据往往被实现为字典树

也许我们不太合适?

但我总感觉这种结构实现为字典树并不太好，路由信息和字典树应用对象有些很明显的不同:

  1. 单词的长度是可预期的，并不会太长。但路由信息是不能预期长度的，可能会导致树的高度失控，当出现 大量长路径且公共祖先遥远的情况下，树可能就退化为了链表
  2. 单词的基本单元是字符，是一个有限集，且西文情况下，这个集合很小，字典树结构能很好的进行处理。 而路由信息的基本单元是单词，可以说是一个无限集，这里又有两种情况:
    1. 坚持以单词为基本单元(相当于压缩字典树)，这个时候每个节点需要引入一个离散映射结构，用来存储 单词 → 节点 的信息 这将导致内存耗用变得难以预测，还有一点就是如果每个节点的数据量不大，在某些离散映射的实现里，可能也会 退化为线性搜索
    2. 以字符为基本单元，但这种情况下西文字符集一般是不够用的，所以常见的做法是转换为字节流进行处理 每个节点需要256个槽，这对于字典来说还好，但是对于路由信息来说，内存耗用可能会变得难以接受， 这种情况开源使用自适应基数树进行解决。缺点就是数据调整时可能除非自适应调整，另外一个很严重的 问题就是，路由信息的行为上主要还是以分隔符分割出来的单词作为基本单元，如果以字符为基本单元， 进行模式匹配时，处理时稍微复杂些

还可以挽回么?

自动机

自动机应该可以实现路由结构，而且搜索性能可能比上面的字典树实现都要快，但内存耗用也应该更加夸张，暂时不考虑

平坦化结构

这种方法实现逻辑如下:

  1. 每条消息路由的，每个从根节点出发的子路径都创建一个映射
  2. 映射的实现有两种: 例子: /i/am/some/topic

    1. 只包含自己的直接子节点 这种情况下，对子树的搜索会以递归的方式完成

      key value
      i am
      i/am some
      i/am/some topic
      i/am/some/topic _

    2. 包含自己的直接子节点和所有后代节点 这种情况下，能很好的完成对某个层级的所有节点的匹配，同时又能很方便的找到所有后代节点

      id key child desc
      1 i am 2, 3, 4
      2 i/am some 3, 4
      3 i/am/some topic 4
      4 i/am/some/topic _ _

这种方式能够很好的处理路由直接查找和子树查找，缺点就是内存耗用比较大

平衡树+映射表

这种实现的逻辑如下:

  1. 引入一颗平衡树(红黑树或者B树)，和字典树一样，将路径中的每个单词做为一个节点,而有序规则如下:
    1. 子路径永远比父路径小
    2. 不同的路径比较时，从根节点依次进行比较，兄弟节点以单词大小进行比较(为了加速比较，可以对字典 进行预先哈希，比较时就直接比较哈希值，不过哈希算法需要保证顺序映射不会颠倒)
  2. 引入一个映射表，类似平坦化结构里面的思路，存储从 根节点 → 某个子节点 的 路径 → 该节点 的映射

应用说明

  • 直接搜索某个路径

    例子: /i/am/some/topic 这种情况，直接查找映射表，通过映射表找到对应的节点即可

  • 搜索子树

    例子: /i/am/+/topic/what 这种情况，搜索分为两步:

    1. 通过映射表找到"i/am“这个路径对应的节点
    2. 从该节点开始搜索所有小于该节点，且树高差距为1的节点
    3. 收集这些节点的名称，比如nameA、nameB、nameC
    4. 将这些名称依次带入搜索路径的 + 处，形成所需路径, 比如”/i/am/nameA/topic/what"，这个时候直接 在映射表中查找对应节点即可