2019年4月

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节点

  1. 节点包含一个元素和两个孩子(或者没有孩子)
  2. 左子树包含的元素值小于该节点的元素值,右子树包含的节点的元素值大于该节点的元素值
  3. 2节点要不有两个孩子,要不就没有孩子,不允许有一个孩子
    2). 3节点
  4. 包含一大一小两个元素(两个元素按大小顺序排列好)和三个孩子(或者没有孩子)
  5. 左子树包含的节点的元素值小于该节点较小的元素值,右子树包含的节点的元素值大于该节点较大的元素值,中间子树包含的节点的元素值介于这两个元素之间
  6. 3节点要么有三个孩子,要么就没有孩子,不允许有一个或两个孩子
    3). 所有叶子节点都在同一个层次

要点

  1. 每次新增或删除节点时可能会触发节点的分裂与合并
  2. 在分裂与合并发生时,有可能会发生连锁的分裂与合并
  3. 2节点有可能会转换为3节点

实现思路

每次在新增或者删除节点时,判断一次当前节点的元素节点有没有超过2(3节点的元素最多为2),有则触发分裂,把当前节点3个值中中间的值向父节点传递,这个动作可能会触发父节点从2节点变为3节点,或者触发从3节点转换为2节点(分裂新节点)