图解B树构建过程

淩亂°似流年 2023-02-20 07:35 29阅读 0赞

# 1.B树结构同时满足以下特性 #

1.  每个节点最多包含n个孩子，即n叉树；
2.  除了根节点和叶子节点外，每个节点至少有ceil(n/2)个孩子（ceil是向上取整）；
3.  若根节点不是叶子节点，则至少有两个孩子；
4.  所有叶子节点在同一层；
5.  ☆☆☆每个非叶子节点由m个key和m+1个指针组成，其中(ceil(n/2)-1)<=m<=n-1；

【B树的非叶子节点示意图】

*  key是存储的值，保存的是数据表某一列的内容
 *  p是指针，指向当前节点的孩子
 *  一个非叶子节点中包括m个key和m+1个指针

![image][]

【伪代码示例】

// 下面是一段伪代码，目的是为了让读者从代码角度更好理解一下B树节点的结构，请不要在意语法是否正确
    struct BTreeNode{
        int n;              // 代表这是n叉树
        int key[m];         // 代表当前类型中key有m个，其中(ceil(n/2)-1)<=m<=n-1
        BTreeNode *p[m+1];  // 代表当前节点由m+1个指针，指向其孩子节点，允许为空
        
    }

# 2.图示构建过程 #

【☆☆☆B树构建原则】

1.  当节点中的key的个数不超过n-1时，按照大小顺序排列插入；
2.  当key的个数大于n-1时，中间key向上分裂到父节点中，两边key分裂成两个节点

`以3叉树为例，插入[1,3,2,5,4,6,7]`

## step1.计算key的个数 ##

(ceil(n/2)-1)<=key<=n-1

`3叉树，所以1<=key<=2`

## step2.往根节点中插入1，3 ##

![image][image 1]

## step3.往根节点中插入2，开始向上分裂 ##

![image][image 2]

## step4.往节点中插入5，4，开始向上分裂 ##

![image][image 3]

## step5.往节点中插入6 ##

![image][image 4]

## step6.往节点中插入7，开始向上分裂 ##

![image][image 5]

[image]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlLzEyNzJFODhCOEY3MjREQThBNzFBMUE5NDAxMzcxQjBFLzE1NDI5?x-oss-process=image/format,png
[image 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlL0Y2Mjc0NjM0Njg1NTQ3OTFBNzBCMzRGMDY1QkE3QjIzLzE1NDQ1?x-oss-process=image/format,png
[image 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlLzdBMzIwQ0NDMEQ2ODQ3NUE5QTQ3RUQyRTRDNjM1NUQ4LzE1NDQ5?x-oss-process=image/format,png
[image 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlLzhEMjIyRTQ2MTgxMDQ4M0JCOEQ0QTZFMjI5OEVGMDY0LzE1NDU0?x-oss-process=image/format,png
[image 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlL0IxQjU1OTA5NUNDMDQ1MjBCQTkzQkMyQzgwNzFBQTUyLzE1NDU5?x-oss-process=image/format,png
[image 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS84MzA2YmQ5OGY3MTU0NDI2YzgyYWU5NzNkM2FiMzc5Ny94bWxub3RlL0RGQjU2QURBNEU3ODQ1OTQ4QkI0OEQ3NEZBRTVDRUQ5LzE1NDU3?x-oss-process=image/format,png