数据结构-树
二查查找树(BST)
特点:
- 会不平衡
- 节点直接的大小关系
自平衡二查查找树(AVL)
AVL可以理解为BST的变种, 可见是在BST基础上加入了自平衡功能
特点:
- 高度平衡: 这也导致了调整树的开销比较大,不适合频繁地插入删除节点
- 红黑树
红黑树可以看成是AVL树的变体,减少了平衡调整的开销
特点:
- 性能好:红黑树的算法时间复杂度和AVL相同,但统计性能比AVL树更高.
- 追求大致平衡,减少平衡树的开销:任何不平衡都会在三次旋转之内解决
- 每个node的结构比较简单(相比btree,因为是二叉的):因此数据结构本身不需要管理内存,较为轻量级。
应用:
- java中的TreeMap
- C++的STL中的map数据结构
skiplist
跳表可以理解成为一个特殊的树。redis用的是跳表的变体ziplist更加节约内存,但是只付出了较少的性能代价。skiplist和红黑树性能是比较接近的,但是使用skipList有如下好处:
- 跳表实现简单
- 跳表是并发友好的数据结构(红黑树在并发环境平衡树时需要锁很多节点)。
参考资料: - 为啥 redis 使用跳表(skiplist)而不是使用 red-black
- Skip List vs. Binary Tree
跳表本质上也是一种随机平衡B树(RBST)
B树(也称作B-树)
一般化的BST,只不过是多路的。相比红黑树的优点,就是明显层数少了。
特点:
- 相比BST也看到了分支多,所以层数少,因此用于索引减少IO次数是不错的
- 多路意味着每个node比较“重”:需要自己管理node结构内存。当然“重”的好处是方便自己做lockfree,一个node存放多个kv可以保证较高的cpu cache命中率。
B+树
B树的变体,和B树主要差别是叶子节点存放数据
特点:
- B树的变体
- 只在叶子节点存放数据
- 叶子节点之间通过一个链表连接在一起,方便遍历
为啥索引更加喜欢用B+树而不是B树?所有好处都是基于数据放叶子节点
- 叶子节点有序存储所有key,遍历所有数据、范围查找更快
- 相同高度下,由于非叶子节点不存放数据,占用空间减小了。这样当索引放在磁盘上时,一次IO可以读取更多的数据。从而减少了读取索引的IO次数
- 由于是多路的,层次低: 这个算是B树都有的特点