数据库系统——B+树索引
原文来自于：http://dblab.cs.toronto.edu/courses/443/2013/05.btree-index.html
1. B+树索引概述
在上一篇文章中，我们讨论了关于index的几个中重要的课题：
A) index是保存在磁盘上的一种数据结构，用于提高查询或是扫描record的速度。
B) 排序索引树通过保存page的指针加速record的查找。（ISAM）
C) 维护排序索引树的代价很高，因此，ISAM通过创建overflow page来解决这个问题，但是过多的overflow page会使查询性能从log（指数log）级别降低到线性遍历。
下面我们将介绍一种高度健壮的、比较流行的一种数据结构——B+树，作为ISAM的扩展。
一般说来，B+树是一种高效的基于磁盘保存的数据结构，主要保存(key, value)pair。它支持对key的高效查找，和高效的范围迭代。
B+树提供了这些功能：
A) 快速的record查找
B) 快速的record遍历
C) 不通过overflow page的形式维护排序树结构
B+树背后的关键思想是利用有序平衡树，替代ISAM中的排序树。
2. B+树的定义
B+树是用磁盘上的page作为node节点的树。B+树中的节点可以区分为leaf node（叶子节点）和interior node（内部节点）。
由于每一个node刚好是磁盘中的一个page，在B+树中，我们使用的术语node和page是可以互换的。
2.1 leaf node
leaf node保存数据entry（条目，相当于record），entry的形式是(key, value)。所有的leaf node也被组织成page链表的形式。B+树的leaf node如下图所示：
下面是leaf node抽象的数据结构定义：
下面是interior node抽象的数据结构定义：
2.3.3 B+树是平衡树
B+树是平衡树，所有从root node到任何leaf node的路径长度是相等的。
2.3.4 B+树node是充分填充的
B+树允许它的node部分填充。主要是设计了一个填充因子的参数，用来限定每个non-root node（非根节点）的最小填充度。
如果一个non-root node的填充度不够，我们就说该node underflow，在B+树里只有root node可以underflow。
这里有一个不合格的B+数的例子。假设我们定义了下面的参数：
Capacity of each node: 4 keys
Fill factor: 50%
当该树经过平衡和排序后，它的结构如下图所示：
它存在着这样一个问题：没有满足我们上面定义的填充因子（fill factor）50%：
3. B+树的查询search和插入insert
B+树的主要操作有：
Case 2：
在这种情况下，target node已满，但是它的parent node有足够的空间保存一个key。
A) 创建一个target node的兄弟node作为new_target node，将new_target node插入带target node之后。
B) 将target node中的所有entry和我们需要增加的entry分配保存到target node和new_target node中。由于分配之前target node是满的，那么就可以断定分配之后，这两个node不会存在underflow。
C) 将new_target的指针(k,p) = (leaf2.keys[0], ADDRESS[leaf2]) insert到target node的parent node中。由于parent node有足够的空间保存一个key，所以parent node不会出现overflow。
如图示：
Case 3：
这种情况是target和parent[target]都满了的情况。我们需要递归的尝试将新的key insert到target的祖先node中。甚至都有这种情况：root node也没有足够的空间保存这个新key ，这种情况下，我们必须对root进行分割，创建一个新的node作为B+树的root node。
具体细节如下：
A) 创建一个new_target node，insert到target之后。
B) 将target中的entry分配保存到target和new_target中。
现在我们需要将new_target node的指针(k,p) = (leaf2.keys[0], ADDRESS[leaf2])插入到它的PARENT[target]，但是PARENT[target]已经满了。
A) 令target_parent = PARENT[target]
B) 令all_keys = sorted(target_parent.keys ∪ {k})
C) 申请一个新的node：new_interior
D) 令i = floor(all_keys.size() / 2)
middle_key = all_keys[i]
E) 将all_keys[0 .. i-1]保存到target_parent中，将all_keys[i+1 .. n]保存new_interior到中。
F) 如果target_parent是root，那么我们就创建一个新的node作为grandparent ，令grandparent = PARENT[target_parent]。
G) 递归地调用：
insert_into_node(grandparent, middle_key, ADDRESS[new_interior])
如图所示：
4. B+树的其它的东西
a) B+树也支持高效的删除delete。删除算法是insert算法的逆过程。在delete的算法中会通过merge（合并）node，去避免underflow。如果发生merge node，那么会在parent node递归的delete这个(Key, PagePointer)。
b) 如果所有的data entry都保存在sequential file中，并且关于key排序，那么就可以非常有效的将sequential file装载到B+树。
c) B+树可以作为基于磁盘有序存储的排序算法。
