oracle技术之B树索引

师傅你而

　　虽然一级或两级索引通常有助于加快查询，但在商用系统中常使用一种更通用的结构。这一通用的数据结构簇称为B树，而最常使用的变体称为B+树。实质上：
　　B树能自动地保持与数据文件大小相适应的索引层次。
　　对所使用的存储块空间进行管理，使每个块的充满程度在半满与全满之间。这样的索引不再需要溢出块。
　　在接下来的内容中，我们将讨论“B树”，但具体细节都针对B+树这一变体。其他类型的B树在习题中讨论。
　　1、B树的结构
　　正如其名称所暗示的那样，B树把它的存储块组织成一棵树。这棵树是平衡的，即从树根到树叶的所有路径都一样长。通常B树有三层：根、中间层和叶，但也可以是任意多层。为了对B树有一个直观的印象，可以先看一下图4-21、图4-22和图4-23，其中前两个图所示的为B树结点，而后一个图所示的为一个小而完整的B树。
　　对应于每个B树索引都有一个参数n，它决定了B树的所有存储块的布局。每个存储块存放n个查找键值和n+1个指针。在某种意义上讲，B树的存储块类似于4.1节讲述的索引块，只不过B树的块除了有n个键-指针对外，还有一个额外的指针。在存储块能容纳n个键和n+1个指针的前提下，我们把n取得尽可能大。
　　例4.19 假定我们的存储块大小为4096字节，且整数型键值占4字节，指针占8字节。要是不考虑存储块块头信息所占空间，那么我们希望找到满足4n+8（n+1）≤4096的最大整数值n。这个值是n=340。
　　下面几个重要的规则限制B树的存储块中能出现的东西：
　　（1）根结点中至少有两个指针被使用。所有指针指向位于B树下一层的存储块。
　　（2）叶结点中，最后一个指针指向它右边的下一个叶结点存储块，即指向下一个键值大于它的块。在叶块的其他n个指针当中，至少有个指针被使用且指向数据记录；未使用的指针可看作空指针且不指向任何地方。如果第i个指数被使用，则指向具有第i个键值的记录。在内层结点中，所有的n+1个指针都可以用来指向B树中下一层的块。其中至少个指针被实际使用（但如果是根结点，则不管n多大都只要求至少两个指针被使用）。如果j个指针被使用，那该块中将有j－1个键，设为K1，K2，Kj-1。第一个指针指向B树的一部分，一些键值小于K1的记录可在这一部分找到。第二个指针指向B树的另一部分，所有键值大小等于K1且小于K2的记录可在这一部分中。依此类推。最后，第j个指针指向B树的又一部分，一些键值大于等于Kj-1的记录可以在这一部分中找到。注意：某些键值远小于K1或远大于Kj-1的记录可能根本无法通过该块到达，但可通过同一层的其他块到达。
　　（3）假若我们以常规的画树方式来画B树，任一给定结点的子结点按从左（第一个子结点）到右（最后一个子结点）的顺序排列。那么，我们在任何一个层次上从左到右来看B树的结点，结点的键值将按非减的顺序出现。

　　例4.20 在这个例子和其他B树实例中，我们设n=3。也就是说，块中可存放3个键值和4个指针，这是一个不代表通常情况的小数字。键值为整数。图4-21所示为一个完全使用的叶结点。其中有三个键值57、81和95。前三个指针指向具有这些键值的记录。而最后一个指针，指向右边键值大于它的下一个叶结点，这正是叶结点中通常的情况。如果该叶结点是序列中的最后一个，则该指针为空。叶结点不必全部充满，但在我们这个例子中，n=3，故叶结点至少要有两个键-指针对。也就是说，图4-21中的键值95和第三个指针可以没有，该指针标有“至键值为95的记录”。

　　图4-22所示为一个典型的内部结点。其中有三个键值，与我们在叶结点的例子中所选的一样：57、81和95。该结点中还有四个指针。第一个指针指向B树的一部分，通过它我们只能到达键值小于第一个键值即57的那些记录。第二个指针通向键值介于该B树块第一个键值和第二个键值之间的那些记录，第三个指针对应键值介于该块第二个键值和第三个键值之间的那些记录，第四个指针将我们引向键值大于该块中第三个键值的那些记录。同叶结点的例子一样，内部结点的键和指针槽也没有必要全部占用。不过，当n=3时，一个内部结点至少要出现一个键和两个指针。元素缺失最极端的情形就是键值只有57，而指针也仅使用前两个，在这种情况下，第一个指针对应于小于57的键值，而第二个指针对应于大于等于57的键值。键值
　　例4.21 图4-23所示为一棵完整的三层B+树；其中使用例4.20中所描述的结点。我们假定数据文件的记录的键是2~47之间的所有素数。注意，这些值在叶结点中按顺序出现一次。所有叶结点都有两个或3个键-指针对，还有一个指向序列中下一叶结点的指针。当我们从左到右去看叶结点时，所有键都是排好序的。根结点仅有两个指针，恰好是允许的最小数目，尽管至多可有4个指针。根结点中的某个键将通过第一个指针访问到的键值与通过第二个指针访问到的键值分隔开来。也就是说，不超过12的键值可通过根结点的第一个子树找到；大于等于13的键值可通过第二个子树找到。

　　图4-23B+树
　　如果我们看根结点的第一个具有键值7的子结点，会发现它有两个指针，一个通向小于7的键，而另一个通向大于等于7的键。注意，该结点的第二个指针只能使我们找到键7和11，而非所有大于7的键，比如键13（虽然我们可以通过叶结点中指向下一个块的指针找到那些更大的键）。
　　最后，根结点的第二个子结点的4个指针槽都被使用。第一个指针将我们引向一些键值小于23的键，即13、17和19。第二个指针将我们引向键值大于等于23而小于31的所有键；第三个指针将我们引向键值大于等于31而小于43的所有键；而第四个指针将我们引向一些键值大于等于43的键（在这个例子中，是所有的键）。
　　2、B树的应用
　　B树是用来建立索引的一种强有力的工具。它的叶结点上指向记录的一系列指针可以起到我们在4.1节和4.2节学过的任何一种索引文件中指针序列的作用。下面是一些实例：
　　1）B树的查找键是数据文件的主键，且索引是稠密的。也就是说，叶结点中为数据文件的每一个记录设有一个键-指针对。该数据文件可以按主键排序，也可以不按主键排序。
　　2）数据文件按主键排序，且B+树是稀疏索引，在叶结点中为数据文件的每个块设有一个键—指针对。
　　3）数据文件按非键属性排序，且该属性是B+树的查找键。叶结点中为数据文件里出现的每个属性值K设有一个键-指针对，其中指针指向排序键值为K的记录中的第一个。
　　B树变体的另一些应用允许叶在结点上查找键重复出现。图4-24所示即为这样一棵B树。这一扩展类似于我们在4.1.5节讨论的带重复键的索引。
　　如果我们确实允许查找键的重复出现，就需要稍微修改对内部结点中键的涵义的定义，我们曾在4.3.1节中讨论过这一定义。现在，假定一个内部结点的键为K1,K2，Kn,那么Ki将是从第i+1个指针所能访问的子树中出现的最小新键。这里的“新”，是指在树中第i+1个指针所指向的子树以左没有出现过Ki，但Ki在第i+1个指针指向的子树中至少出现一次。注意，在某些情况下可能不存在这样的键，这时Ki可以为空，但它对应的指针仍然需要，因为它指向树中碰巧只有一个键值的那个重要的部分。

　　例4.22 图4-24所示的B树类似于图4-23，但有重复键值。具体来说：键11已被键13替换；键19、29和31全部被键23替换。这样就造成根结点的键是17而不是13。原因在于，虽然13是第二个子树根结点中最小的键，但它不是该子树的新键，因为它在根结点的第一个子树中出现过。
　　我们还需要对根结点的第二个子结点做些改变。第二个键改为37，因为它是第三个子结点（从左数第五个叶结点）的第一个新键。最有趣的是，第一个键现在为空，因为第二个子结点（第四个叶结点）根本就没有新键。换言之，如果查找某个键且到达根结点的第二个子结点，我们不会从该子结点的第二个子结点起开始查找。若是查找23或其他更小的值，我们应该从它的第一个子结点起开始查找，在那里我们将找到所需的记录（如果是17），或找到所需的记录的第一个（如果是23）。
　　注意：
　　（1）查找13时我们不会到达根结点的第二个子结点，而是直接到第一个子结点中去查找。
　　（2）如果查找介于24~36之间的某个键，我们会直接到第三个叶结点中查找。但当我们连一个所需键值都找不到时，我们就知道不必继续往右查找。举例来说，如果叶结点中存在键24，它要么在第四个叶结点上，这时根结点的第二个子结点中的空键将会被24替代；要么在第五个叶结点上，这时根结点的第二个子结点的键37将被24替代。
　　3、B树中的查找
　　我们现在再回到最初的假定，即叶结点中没有重复键。这个假定可以简化对B树操作的讨论，但该假定对这些操作来说并非必不可少。假设我们有一个B树索引并且想找出查找键值为K的记录。我们从根到叶递归查找，查找过程为：
　　基础：若处于叶结点，我们就在其键值中查找。若第i个键是K，则第i个指针可让我们找到所需记录。
　　归纳：若处于某个内部结点，且它的键为K1,K2,,Kn，则依据在4.3.1节中给出的规则来决定下一步该对此结点的哪个子结点进行查找。也就是说，只有一个子结点可使我们找到具有键K的叶结点。如果K
　　例4.23 假定有一棵如图4-23所示的B树，且我们想找到查找键为40的记录。我们从根结点开始，其中有一个键13。因为13≤40，我们就沿着它的第二个指针来到包含键为23、31和43的第二层结点。
　　在这个结点中，我们发现31≤40＜43，因而我们沿着第三个指针来到包含31、37和40的叶结点，如果数据文件中有键值为40的记录，我们就应该在这个叶结点中找到键40。既然我们没有发现键40，就可以断定在底层的数据块中没有键值为40的记录。
　　注意，要是查找键为37的记录，我们所做的决定都和上面一样，但当到达叶结点时，我们将找到键37。因为它是叶结点中的第二个键，因此我们沿着第二个指针可以找到键值为37的数据记录。
　　4、范围查询
　　B树不仅对搜寻单个查找键的查询很有用，而且对查找键值在某个范围内的查询也很有用。一般来说，范围查询在Where子句中有一个项，该项将查找键与单个值或多个值相比较，可用除“=”和“”之外的其他比较操作符。使用查找键属性K的范围查询例子如下：
　　select * form R where R.k > 40;
　　或者
　　select * form R where R.k > 10 and R.k