B-树

为什么需要B-树

当所有数据都存储在内存中时，用红黑树的查找性能已经非常的好了。但是当数据量非常的大的时候，把数据存放在内存中显然是不可取的，这个时候就会想到把数据存放在磁盘中，再进行查询操作。但是有频繁的磁盘I/O操作（磁盘查找数据时是机械运动），会降低效率，普通二叉树的高度决定了磁盘I/O的时间。如果把相关的信息放在相近的地方，这样在磁盘中就会被存放为同一个数据块，减少磁盘中磁头的移动查找，从而减少I/O的时间。B-树就是这样一种数据结构。

B-树的定义和性质

B-tree其实就是B树。

一颗m阶B树定义：

1. 每个节点至多有m个子树
2. 除了根节点以为，每个节点至少有m/2棵子树
3. 根节点至少有两颗子树
4. 所有叶子节点在树结构的同一层，并都不包含任何信息（可以看做是外部节点或查找失败的节点），因此m阶B树总是树高平衡的
5. 有k个孩子的非叶节点恰好有k-1个关键码，关键码按递增顺序排列

B-树的查找、插入、删除操作过程

• 查找过程分两步，从B树的根节点开始：

  1. 在当前节点中对关键字进行二分法查找。如果找到关键字，就返回相关记录，如果当前节点时叶子节点，就报告检索失败。
  2. 否则，沿着其中某一分支重复这一过程。

• 插入操作：
  找到最下层的内部节点，如果节点的孩子个数小于m，那么就直接插入关键字；如果节点的孩子个数等于m，那么就把这个节点分裂成两个节点，并且把中间的关键字提升到父节点。如果父节点也已经满了，就再分裂父节点，并且再次提升中间的关键字。插入过程保证所有节点至少半满。

• 删除操作：
  首先找到包含被指定关键字的节点，并从中删除，如果节点为最下层的内部节点，且其中的孩子个数大于m/2，则删除完成；否则要进行“合并操作”或从相邻兄弟中借一个关键字，如果所删除的关键字不是最下层的节点，则在此关键字右邻子树中最右边的最下层中的最小关键字取出并替换删除的节点的值，然后再删除那个最小关键字节点。