GBASE 8s 索引B+树

        数据库常用的索引结构有二叉搜索树、B 树，B+树、Hash、位图和R 树，其中使用最广泛的是 B+树。本节重点描述 B+树索引结构。 B+树可以看作改进的 B 树，在介绍 B+树之前，我们先来看看B 树的索引结构，如图所示。B 树把各个存储块组织成一棵树的形式，这棵树总是保持平衡的，即所有叶子节点总具有相同的深度。B 树中有三种节点：根节点、分支节点和叶子节点。根节点指向多个分支节点，分支节点指向叶子节点，叶子节点指向实际的数据行地址。

        一棵 m 阶 B 树是一棵平衡的 m 路搜索树，每个存储块（节点）存储m个关键字和m+1个指针。它或者是空树，或者是满足如下性质的树。

1. 根节点至少包含两个子节点，即至少有两个指针被使用，每个指针指向B树的下一层存储块。
2. 总是保持数据的有序性，每个存储块中的关键字按递增顺序排列。
3. 分支节点至少有（m +1）/2 个指针被使用。假设在某块中使用了j 个关键字，设为 K1，K2，…，Kj（K1＜K2＜…＜Kj），那么该块有j +1 个指针被使用，每一个指针指向 B 树的下一层节点。其中第一个指针指向关键字小于K1 的记录部分，第二个指针指向关键字大于等于 K1且小于 K2 的记录部分，以此类推，第j 个指针指向关键字大于等于 Kj-1且小于 Kj的记录部分，最后一个指针指向关键字大于等于 Kj的记录部分。
4. 在叶节点中最后一个指针指向它右边的下一个叶节点，即下一个关键字大于它的存储块。其他 m 个指针至少要有（m +1）/2 个被使用，每一个指针指向实际的数据记录。如果第 j 个指针被使用，那么它指向具有该块中第j 个关键字的记录。

        因此，这些节点可以是不完全填充的，每种节点的填充程度（即关键字个数）必须大于某个最小的百分比值，其余没有被填充的空间是浪费掉的。

        B 树的这种存储结构保证了搜索、插入和删除操作的时间复杂度在对数级内。在搜索时从根到叶节点递归查找，将需要查找的关键字和根节点（分支节点）中的各个关键字进行了对比（可用顺序查找法或二分查找法），找到该关键字存在的区间，根据指针递归查找下一层节点，直到叶节点为止，即可找到叶节点指向的实际数据行地址。插入时，B树从最底层开始增长，当节点溢出（关键字个数多于 m 个）时，节点自动分裂，新节点会被提升到高一级的层数上，删除时操作正好相反。

        为了更进一步理解 B 树结构，下面举例说明插入数据导致节点分裂的情况，如图8.5所示。这里假设每个节点只能存放 4 个关键字（m = 4），那么当向一个已存满4 个关键字的节点中新增一条记录时，节点将进行分裂，并将中间的关键字提升到上一层中。关键字的提升可能会导致上一层节点继续分裂，如果根节点也已经存满了4 个关键字，那么根节点将会分裂，此时树高增加一层会同时创建一个新的根节点。分裂后，节点中会有空闲位置，可以在新增记录时使用。

        在 GBase 8s 数据库中，B+树的索引结构如图 8.7 所示，每个索引节点都是双向连接的，都有指向前一个和后一个同级节点的指针，这样可以进行区间范围的查询，在同级节点间也可以进行正序和逆序搜索，大大提高了索引在数据搜索中的性能。一个节点向左或向右跳转到它的兄弟节点的能力是 B+树的一个亮点，GBase 8s 数据库中的所有非多维数据索引都是 B+树索引。