学步园

1.B树的基本思想

   B树的每个节点都是一个页面。B树有两种类型的节点：叶子节点和索引节点。叶子节点包含要查找的数据，对聚集索引而言数据是记录，对非聚集索引，这里的数据是指索引列、主关键字（或ROWID）。索引节点不包含数据，只包含下一层节点的路由信息。

   B树索引节点的抽象数据结构如下：

ulint      F;             //在一个索引节点中最大入口项的数量

struct

{

  char     *K;           //B树的key值

  PAGEID   P;            //指向其它页面的指针

}index_node_structure[];    //有key-指针所组成的数组

   这里F定义了每个页最多存放的索引项（也可称为入口项）的数量，在实际的数据库实现当中，不会定义该数值。比如，假设在varchar列上建立索引，那么索引项的大小就是变长的，因此索引节点中存放的索引项的数量也是变化的。为了便于叙述的方便，这里设定了该值F。

K_i标识数组的第i个成员。每个索引节点包含一个有序的索引键值K₁≤K₂≤…≤K_F,它们对这个节点的查找空间加以划分。每个索引键值K_i的后面都跟着一个指向其它后继节点的指针P_i,该后续节点包含位于K_i和K_i+1之间的那些索引键值K_j（K_i≤K_ji+1）有关的所有信息。同样，小于索引键值K₁的信息保存在P₀指向的子树中。

   上面申明的结构中包含一个附加的索引键值K₀，它正好位于索引序列的开始处。如果规定P₀指向的子树中包含所有小于K₁的索引值，那么实际上不需要该索引值（也就是，index_node_structure[0]中的K成员的值无意义）。尽管如此，大多数的B树实现中还是包含该字段的，这使得节点的内部结构变得更加简单：因为可以统一使用规则的<索引键值，指针>对数组结构，而不必使用另外一个指针。

   所有的内部节点都包含这种路由信息，即索引键和指向下层节点的指针，在下层节点中含有更详细的信息。

   叶子节点基本上也是相同的结构，但不包含其它节点的指针。需要注意的是，在索引节点中第一个记录K₀是无意义的，但对叶子节点来说，它却是重要的，是该叶子节点的第一个元组。

2.B树上的查找操作

        参照图1，描述一个查找属性值=s的检索元组的操作。查找总是根节点开始，根节点是一个索引节点。令m（m≤F）为当前节点中具有最大索引键值的入口项索引，则存在以下两种情况：

  1）若s≥K_m，则转到P_m指向的子树；否则，

  2）转到指针P_j指向的子树，这里K_i≤sj+1。

     如果指针指向的节点是一个索引节点，那么重复以上过程。最终指针将会指向一个叶子节点。索引键值=s的元组要么在该叶子节点中，要么根本不存在。在叶子节点内部进行的查找是利用二分查找。

      对于s≤属性值≤t形式的范围查询，因为B树在叶子页之间存在全序。所以该范围查找的执行过程为：

     1）沿B树向下查找值范围的下限，即执行属性值=s的精确匹配查询。这样定位的元组是满足该查找条件的第一个元组。

     2）沿着叶子节点中该记录向后扫描，只要是符合≤t的就符合，如果扫描到该叶子节点的尾部，则跳到它的右兄弟页节点。数据库的页中会保存左、右兄弟的节点指针。重复这样的执行过程，直到元组的索引键值超过上限t或者最后一个叶子节点被处理完。

     当然，如果是降序生成元组，其处理过程也是一样的，只不过是按上限到下限的顺序进行处理。