MySQL 二叉树 AVL树红黑树 B-树 B+树 B*树

寻梦xunm| 711| 收集

3年前

超过1211天温馨提示

本文最后更新于2021年05月27日，已超过1211天没有更新，若内容或图片失效，请留言反馈。

二叉树
一个节点最多只有两个子节点
树的层级结构比较深
左右两边数据层级不一致,查询的层级数量不稳定

平衡二叉树 (AVL)
一个节点最多只有两个子节点
左右两边层级深度差不能大于1
数据量大时,树的层级比较深
插入删除的效率低,查询效率高

红黑树 (red / black tree)
旋转 + 变色
左右两边最长深部不能大于最短深度的两边
一条链中不能出现两个相连的红色
一个节点中的两个链中黑色节点是一样的
AVL树的一个升级,提升了增删的效率

左旋右旋

B树
每一个节点都保存数据
树的层级数量可以指定
每一个节点可以保存4K的倍数数据集(不单单指保存一个值)
预读的概念
由于每一个节点都保存数据,导致节点保存的数据量有限
比如一个节点保存16K数据,每一个数据大小为1K,那一个节点只能保存16个值
如果树有三层,每一个节点保存16个数据,三次IO最多保存161616 (4096个) 数据
因为存储的数据量太少,所以有了B+树

B+树
只有子节点才保存数据
所以相同的IO次数下,跟B-树相比,可以保存更多的数据

B* 树
每一个非子节点保存了下一个非子节点的地址
B*树插入时，当一个节点满时，如果它的下一个兄弟节点未满，那么将一部分数据移到兄弟节点中，再在原节点插入关键字，最后修改父节点中兄弟节点的关键字（因为兄弟节点的关键字范围改变了）。如果兄弟节点满了，则在原节点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的指针。
由于MySQL B+树非子节点不保存数据,所以没使用