1_B树和B+树

(1) 当树保存在磁盘上时，由于磁盘读写速度远远慢于CPU计算速度，所以要尽量减少磁盘IO次数，即便要更多计算的计算量也是值得的

(2) 如果查找树保存在磁盘上，为了减少磁盘的IO次数，基本策略就是减少树的高度，减少树的高度意味着增加每个结点的分叉个数

(3) B树和B+树都是M叉平衡树

B树

(1) 定义

M阶B树

1° 根结点至少有两个儿子，至多有M个儿子

2° 除了根结点和叶结点，中间结点至少有 M/2个儿子，至多有M个儿子

3° 若某个中间结点有s个儿子，则它有 n = s-1 个key值(K1,K2,...,Kn)，该结点要保存的是信息是

(n, A0, K1, R1, A1, K2, R2, A2, ... , Kn, Rn, An)

n：key值的个数

A0: 小于K1的儿子结点的指针

Ai(i=1,2,...,n): 大于Ki且小于Ki+1的儿子结点指针（两边都没有取等)

R1: 等于K1的数据记录在磁盘中的地址

4° 所有叶结点在同一层，且不带任何信息

(2) 在设计时，应该将一个磁盘块作为一个B树的结点，根据每个结点的最大大小和磁盘块的大小，确定阶数

(3) B树可以用作稠密索引

(4) 存在问题

1° 稠密索引，占用空间大

2° 当需要按照索引键顺序访问文件中所有记录时，每次都需要先在B树中查找它的位置，效率低下

B+树

(1) 既可以实现快速的随机访问，又可以实现快速的顺序访问

(2) 定义

1° 根结点至少有两个儿子，至多有M个儿子

2° 除了根结点，其他结点至少有 M/2个儿子，至多有M个儿子

3° 有k个儿子的结点，保存了k-1个键来引导查找，键i代表了子树中键的最小值（大于等于的关系）

4° 叶结点的儿子指针指向存储记录的数据块的地址

5° 每个数据块至少有 [L/2]个记录，至多有L个记录

6° 为了加快顺序访问的速度，某些定义中对叶结点增加一条链，将所有的叶结点按照从左到右的次序连成单链表

(3) 和B树的区别

1° 其他结点不保存记录的地址，统一由叶结点保存，使得每个结点保存的信息量减少，树的阶数可以增加，树的高度降低

2° 叶结点连在一起，适合顺序访问

(4) B+树的基本策略

1° 分块查找的思想：每个索引键值对应的是一个数据块中的最小数值，数据块内部可以无序（因为数据数目有限），但是块和块之间要有序

2° 不把数据块装满：至少[L/2]个记录，至多L个记录，大多数情况下插入、删除时只需要在所在的数据块改动即可; 所在块装满或者小于[L/2]时再调整父子结点关系，这种情况遇到的会比较少

(5) 阶数M和数据块中最多记录数L的计算

应该让每个结点代表一个磁盘块，提高磁盘IO效率

示例

  设一个磁盘块的容量 8192B，每个记录长为256B, 索引键值的长度 32B；

  M阶树中每个结点最多有 M-1个键值，占用 32(M-1) B; 设每个地址（磁盘块地址、指针地址）占用4B，最多占用 4M B，所以每个结点的最大占用空间为 32(M-1) + 4M = 36M - 32 <= 8192, M <= 228.44 = 228;

  256L <= 8192, L <= 32 = 32.

(6) 查找操作

对每个结点比较结点中的所有K值，据此找到子结点分支，直到查询到叶结点对应的数据块

(7) 插入操作

根据查找操作，首先寻找要插入的数据块的位置

1° 如果插入后，数据块满足小于等于L,则直接插入

2° 如果插入后，数据块溢出，则分裂当前数据块为2个数据块，同时更新叶结点中的key值信息

2.1° 如果叶结点中的儿子数量仍然不大于M个，则直接更新即可

2.2° 如果叶结点中的儿子数量大于M个，则递归地进行：分裂子结点，更新父结点的信息，直到根结点。如果根节点的儿子数量也大于M个，则分裂根结点，上方添加新的根节点，这是B+树长高的唯一情况

(8) 删除操作

根据查找操作，首先寻找要删除的数据块的位置

1° 如果删除后，数据块满足大于等于大于等于[L/2]，则直接删除

2° 如果删除后，数据块数量小于[L/2]，则合并相邻的数据块，同时更新叶结点中的key值信息

2.1° 如果叶结点中的儿子数量仍然不小于 [M/2]个，则直接更新

2.2° 如果叶结点中的儿子数量小于 [M/2]个，则递归地进行：合并子结点，更新父结点的信息，直到根结点。如果根结点的儿子数量也小于[M/2]个，则删除根，让儿子作为新的根，这是B+树变矮的唯一情况