B+ Trees¶
Definition¶
A B+ tree of order M is a tree with the following structural properties:
- 我们不能有一个根加一个孩子的结构
- 这棵树是从下往上构建的，而非从上往下
Operation¶
Insertion¶
- Simple spliting method
- find a not full sibling(\(\times\))
- 从中我们可以看到，叶子节点元素个数最多有M个
Deletion¶
与插入相似，但在一个节点失去两个孩子后，需要删掉它
Analysis¶
因为在最坏的情况下，每个节点只有M/2个节点
Problem¶
1¶
D
Don't know.
2¶
A
很简单，定义