mysql底层数据结构之--BTree结构及相关数据结构了解

时间:2024-05-20 17:59:19

BTree特性

BTree又叫多路平衡查找树,一颗m叉的BTree特性如下:

  • 树中每个节点最多包含m个孩子。
  • 除根节点与叶子节点外,每个节点至少有[ceil(m/2)]个孩子。
  • 若根节点不是叶子节点,则至少有两个孩子。
  • 所有的叶子节点都在同一层。
  • 每个非叶子节点由n个key与n+1个指针组成,其中[ceil(m/2)-1] <= n <= m-1 。

 

mysql底层数据结构之--BTree结构及相关数据结构了解

 

BTree插入

以5叉BTree为例,key的数量:公式推导[ceil(m/2)-1] <= n <= m-1。所以 2 <= n <=4。当n>4时,中间节点分裂到父节点,两边节点分裂。

1、以插入C N G A H E K Q M F W L T Z D P R X Y S为例,前4个字母没什么好说的。

mysql底层数据结构之--BTree结构及相关数据结构了解

2、插入H,n>4,中间元素G字母向上分裂到新的节点。

mysql底层数据结构之--BTree结构及相关数据结构了解

3、插入E,K,Q不需要分裂。

mysql底层数据结构之--BTree结构及相关数据结构了解

4、插入M,中间元素M字母向上分裂到父节点G。

mysql底层数据结构之--BTree结构及相关数据结构了解

 

5、插入F,W,L,T不需要分裂。

mysql底层数据结构之--BTree结构及相关数据结构了解

6、插入Z,中间元素T向上分裂到父节点中。

mysql底层数据结构之--BTree结构及相关数据结构了解

 

7、插入D,中间元素D向上分裂到父节点中。然后插入P,R,X,Y不需要分裂。

mysql底层数据结构之--BTree结构及相关数据结构了解

 

8、最后插入S,NPQR节点n>5,中间节点Q向上分裂,但分裂后父节点DGMT的n>5,中间节点M向上分裂。需要注意的是,原BTree第三个子节点HKL会包含DG节点中。

 

mysql底层数据结构之--BTree结构及相关数据结构了解

到此,一个BTree的构建就完成了,怎么样?是不是很简单。删除操作比插入略微复杂,鉴于篇幅,不做叙述。