B+树研究1 - 2-3树实现
最近在看MySQL的书,经常提到B+树,总是感觉有一层面纱蒙在上面,好神秘。。。
于是决定研究下B+树,在B站上面搜了下B+树的视频,只找到了将B树的视频,配合在网上找的一些资料,得到了一个结论
2-3树和2-3-4树是一种特殊的B树,而B+树是B树的优化版,有点类似于亚古兽-》暴龙兽-》机械暴龙兽-》战斗暴龙兽的意思。
于是决定先实现下简单点的2-3树
2-3树定义
2-3 树是一种多路查找树 :2和3的意思就是2-3树包含两种节点
1). 2节点
- 节点包含一个元素和两个孩子(或者没有孩子)
- 左子树包含的元素值小于该节点的元素值,右子树包含的节点的元素值大于该节点的元素值
- 2节点要不有两个孩子,要不就没有孩子,不允许有一个孩子
2). 3节点 - 包含一大一小两个元素(两个元素按大小顺序排列好)和三个孩子(或者没有孩子)
- 左子树包含的节点的元素值小于该节点较小的元素值,右子树包含的节点的元素值大于该节点较大的元素值,中间子树包含的节点的元素值介于这两个元素之间
- 3节点要么有三个孩子,要么就没有孩子,不允许有一个或两个孩子
3). 所有叶子节点都在同一个层次
要点
- 每次新增或删除节点时可能会触发节点的分裂与合并
- 在分裂与合并发生时,有可能会发生连锁的分裂与合并
- 2节点有可能会转换为3节点
实现思路
每次在新增或者删除节点时,判断一次当前节点的元素节点有没有超过2(3节点的元素最多为2),有则触发分裂,把当前节点3个值中中间的值向父节点传递,这个动作可能会触发父节点从2节点变为3节点,或者触发从3节点转换为2节点(分裂新节点)