在一棵空的5阶B+树上依次插入11、4、10、7、20、19、2、12、13、0、18、17、15、9、8、1、16、3、5、6、14,设L=3,画出这颗B+树
时间: 2023-09-28 20:04:23 浏览: 294
基于C++进行B+树的模拟【100012527】
以下是插入过程中B+树的变化情况,每个节点下方数字表示该节点存储的关键字:
1. 插入11,生成根节点:
```
[11]
```
2. 插入4,生成新的叶子节点,同时更新根节点:
```
[4]
/ \
[11] [ ]
```
3. 插入10,插入到[4]节点中:
```
[4, 10]
/ | \
[11] [ ]
```
4. 插入7,插入到[4]节点中:
```
[4, 7, 10]
/ | | \
[11] [ ]
```
5. 插入20,生成新的叶子节点,同时更新根节点:
```
[7] [11]
/ \ / \
[4,5] [10] [14,16,18] [20]
```
6. 插入19,插入到[14,16,18]节点中:
```
[7] [11]
/ \ / \
[4,5] [10] [14,16,18,19] [20]
```
7. 插入2,插入到[4,5]节点中:
```
[7] [11]
/ \ / \
[2,4,5] [10] [14,16,18,19] [20]
```
8. 插入12,插入到[11]节点中:
```
[7] [11, 12]
/ \ / | \
[2,4,5] [10] [14,16,18,19] [20]
```
9. 插入13,插入到[14,16,18,19]节点中:
```
[7] [11, 12]
/ \ / | \
[2,4,5] [10] [13,14,16,18,19] [20]
```
10. 插入0,插入到[2,4,5]节点中:
```
[0,2,4,5] [7] [11, 12]
/ \ / | \
[ ] [10] [13,14,16,18,19] [20]
```
11. 插入18,插入到[14,16,18,19]节点中:
```
[0,2,4,5] [7] [11, 12]
/ \ / | \
[ ] [10] [13,14,16,18,19,18] [20]
```
12. 插入17,插入到[14,16,18,19]节点中:
```
[0,2,4,5] [7] [11, 12]
/ \ / | \
[ ] [10] [13,14,16,17,18,19,18] [20]
```
13. 插入15,插入到[14,16,17,18,19]节点中:
```
[0,2,4,5] [7] [11, 12]
/ \ / | \
[ ] [10] [13,14,15,16,17,18,19,18] [20]
```
14. 插入9,插入到[7]节点中:
```
[0,2,4,5] [7, 9] [11, 12]
/ | \ / | \
[ ] [2,4,5] [10] [13,14,15,16,17,18,19,18] [20]
```
15. 插入8,插入到[7]节点中:
```
[0,2,4,5] [7, 8, 9] [11, 12]
/ | \ / | \
[ ] [2,4,5] [10] [13,14,15,16,17,18,19,18] [20]
```
16. 插入1,插入到[0,2,4,5]节点中:
```
[0, 1, 2, 4, 5] [7, 8, 9] [11, 12]
/ | \ / | \
[ ] [2,4,5] [10] [13,14,15,16,17,18,19,18] [20]
```
最终的B+树如下所示:
```
+-------+
| 11 |
+-------+
|
+---------------------+
| | |
+-------+ +-------+ +-------+
| 4 | | 7 | | 11 |
+-------+ +-------+ +-------+
| | |
+-------+ +-------+ +-------+ +-------+
| 0 1 2 | | 4 5 | | 7 8 9 | | 10 |
+-------+ +-------+ +-------+ +-------+
| | |
+-------+ +-------+ +-------+
| 13 14 | | 16 17 | | 18 19 |
+-------+ +-------+ +-------+
| |
+-------+ +-------+
| 15 | | 18 |
+-------+ +-------+
|
+-------+
| 20 |
+-------+
```
阅读全文