数据结构-树

二查查找树(BST)

image.png

特点:

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

自平衡二查查找树(AVL)

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

image.png

特点:

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

特点:

  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,只不过是多路的。相比红黑树的优点,就是明显层数少了。

image.png

特点:

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

B+树

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

特点:

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

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

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

参考资料