1. 介绍

今天技术群突然讨论起来树这种数据结构了。我也有些知识点忘了,现在用比较精简的话简单总结下。

2. 二查查找树(BST)

特点:

  1. 会不平衡
  2. 节点直接的大小关系

3. 自平衡二查查找树(AVL)

AVL可以理解为BST的变种, 可见是在BST基础上加入了自平衡功能

特点:

  1. 高度平衡: 这也导致了调整树的开销比较大,不适合频繁地插入删除节点

4. 红黑树

红黑树可以看成是AVL树的变体,减少了平衡调整的开销

特点:

  1. 性能好:红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高.
  2. 追求大致平衡,减少平衡树的开销:任何不平衡都会在三次旋转之内解决
  3. 每个node的结构比较简单(相比btree,因为是二叉的):因此数据结构本身不需要管理内存,较为轻量级。

应用:

  1. java中的TreeMap
  2. C++的STL中的map数据结构

PS: 关于红黑树我们其实还可以思考下redis为啥使用跳表(redis用的是跳表的变体ziplist更加节约内存,但是只付出了较少的性能代价)而不使用红黑树?两者性能差不多,不过:

  1. 跳表实现简单
  2. 跳表是并发友好的数据结构(红黑树在并发环境平衡树时需要锁很多节点)。

参考资料:

  1. 为啥 redis 使用跳表(skiplist)而不是使用 red-black
  2. Skip List vs. Binary Tree

这里也注意,跳表本质上也是一种随机平衡B树(RBST)

5. B树(也称作B-树)

一般化的BST,只不过是多路的。相比红黑树的优点,就是明显层数少了。

特点:

  1. 相比BST也看到了分支多,所以层数少,因此用于索引减少IO次数是不错的
  2. 多路意味着每个node比较“重”:需要自己管理node结构内存。当然“重”的好处是方便自己做lockfree,一个node存放多个kv可以保证较高的cpu cache命中率。

6. B+树

B树的变体,和B树主要差别是叶子节点存放数据

特点:

  1. B树的变体
  2. 只在叶子节点存放数据
  3. 叶子节点之间通过一个链表连接在一起,方便遍历

为啥索引更加喜欢用B+树而不是B树?所有好处都是基于数据放叶子节点

  1. 遍历所有数据更快
  2. 相同高度下,由于非叶子节点不存放数据,占用空间减小了。这样当索引放在磁盘上时,一次IO可以读取更多的数据。从而减少了读取索引的IO次数
  3. 由于是多路的,层次低: 这个算是B树都有的特点

7. 总结

其实树还有好多,常见的就这些。特别是B+树应用很广泛,应该知道。另外跳表这种兴起的数据结构也是一定要知道下的。

参考资料:

  1. 浅谈AVL树,红黑树,B树,B+树原理及应用
  2. 维基百科-红黑树
  3. 为什么有关MongoDB采用B树索引,以及Mysql B+树做索引?
  4. AVL树,红黑树,B树,B+树,Trie树都分别应用在哪些现实场景中?