查找树

Tree Based Search Algorithms:基于树的搜索算法

  • AVL:最早的平衡二叉树之一,早期有应用在linux内核上，后来被RBtree代替了。两者都保持log(n)的插入与查询，是平衡的BST，不会出现(n2)的糟糕情况。但是AVL是一种高度平衡的二叉树，所以通常的结果是，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多。如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。

  • 红黑树:广泛用在C++的STL中,map和set都是用红黑树实现的。其他的著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块、epoll在内核中的实现，用红黑树管理事件块、nginx中，用红黑树管理timer等、Java的TreeMap实现。

  • B/B+:运用在file system database这类持续存储结构，同样能保持lon(n)的插入与查询，也需要额外的平衡调节。像mysql的数据库定义是可以指定B+索引还是hash索引。

  • Tire:大都用在word的匹配，但单纯的trie内存消耗很大，建trie树也需要些时间，通常用在带词典的机械分词，jieba分词就是建立在trie上匹配的，trie有其他变体可以压缩空间，像double array trie这类比较老且经典的压缩方法，也有其他比较新的压缩方式，看论文时有看过，没自己实现过所以不断言了，其实面对多模匹配trie没有其变体aho-corasick来得理想，另外aho-corasick也是可以用巧妙的方法来进行压缩空间，这里不再展开，毕竟手机码字，同时想基数树与其也类似，在nginx上有应用，说到aho-corasick其实早期的入侵检测工具snort也有应用实现，但如今改成wu-menber了，具体记不清了，其实trie还是挺有用的，Tengine也用trie实现了了匹配模块。但要是用在大量单词的匹配上确实吃内存。

Links

最近更新于0001-01-01