- B+ tree是平衡二叉树
- 每个节点包含k个元素, k的范围在 d <= k <= 2d 之间（也就是Minimun 50% occupancy, except for root)
- d 被叫做 the order of the tree
- 比如d = 2，则 2 <= k <= 4, k最小是2, 保证 Minimun 50% occupancy
- 叶子节点用链表相连
- B+ 的主要功能是作为数据库的索引
- 节点只存索引, 叶子节点存数据
- 时间复杂度为
log f N \log_{f}{N} logfN
f = f a n o u t , N = 叶子节点 . f = fanout, N = 叶子节点. f=fanout,N=叶子节点.- B+树高度计算公式
h = l o g d ′ [ ( n + 1 ) 2 d ′ ′ ] + 1 h = log_{d'}{[\frac{(n+1)} {2d''}]} + 1 h=logd′[2d′′(n+1)]+1
其中 d ′ 为内部节点的度数 , d ′ ′ 为叶子节点的度数 其中d'为内部节点的度数, d''为叶子节点的度数 其中d′为内部节点的度数,d′′为叶子节点的度数
Example: 假设有3000W条数据，每个节点保存64个索引. 计算B+树的高度
- 计算B+树的叶子节点的度数： 每个节点最多可以保存64个索引，因此叶子节点的度数也为64. 也就是 d’’ = 64
- 计算B+树的内部节点的度数：由于B+树的叶子节点与内部节点的结构不同，因此它们的度数也不同。对于B+树的内部节点，其度数需要满足以下条件：每个节点内最少包含2个子节点（即分支数至少为2），最多包含64个子节点。因此，可以选择一个适当的度数d’，使得一个节点可以容纳足够多的子节点，同时保持树的平衡性。常见的做法是将d’设置为B+树的叶子节点度数的一半，即d’ = 32
h = l o g 32 [ ( n + 1 ) 2 d ′ ′ ] + 1 h = log_{32}{[\frac{(n+1)} {2d''}]} + 1 h=log32[2d′′(n+1)]+1
假设有3000W条数据，每个节点保存64个索引。
那么索引的高度就是（log2^25）/log64=25/6=4
Insert 16.5
Insert 17
Insert 8
- 左边第一个node已经满了, 则需要拆分node
- 2 3 5 7 8 重新组成两个节点 2 3 和 5 7 8，同时需要将5放进root作为新的索引
- root此时也满了 5 13 17 24 30, 则需要分裂root为两个新node 5 13和24 30, 17作为新的root
Insert 40
delete 19
delete 20
- 22这个节点元素太少, 不符合 Min 50% rule, 所以从旁边的sibling 借元素填充
delete 24
- 左右两边的sibling 都只有min数量的元素, 所以不能借
- 需要合并两个节点
- 合并后父节点只剩一个元素, 所以需要将root和子节点合并
