数据结构-树

二查查找树(BST)

特点:

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

自平衡二查查找树(AVL)

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

特点:

  • 高度平衡: 这也导致了调整树的开销比较大,不适合频繁地插入删除节点
  1. 红黑树
    红黑树可以看成是 AVL 树的变体,减少了平衡调整的开销

特点:

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

应用:

  • java 中的 TreeMap
  • C++的 STL 中的 map 数据结构

skiplist

跳表可以理解成为一个特殊的树。redis 用的是跳表的变体 ziplist 更加节约内存,但是只付出了较少的性能代价。skiplist 和红黑树性能是比较接近的,但是使用 skipList 有如下好处:

  1. 跳表实现简单
  2. 跳表是并发友好的数据结构(红黑树在并发环境平衡树时需要锁很多节点)。
    参考资料:
  3. 为啥 redis 使用跳表(skiplist)而不是使用 red-black
  4. Skip List vs. Binary Tree

跳表本质上也是一种随机平衡 B 树(RBST)

B 树(也称作 B-树)
一般化的 BST,只不过是多路的。相比红黑树的优点,就是明显层数少了。

特点:

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

B+树

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

特点:

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

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

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

参考资料