b 树介绍

B*树是一种可以利用最少的硬盘读取次数在非常大的信息中进

行指针查找的好方法。在B*树中，所有的信息要么是一个分支/根

节点，要么是叶节点。一般来说，最终信息（ROWID与关键字）

都存储在叶节点上。在Oracle7.x中，最多可以有16个列构成关键

字；而在Oracle8中，最多可以有32个列构成关键字。而且，关键

字的大小不能超过数据库块大小的1/3，否则将会导致ORA-0145

0错误。一个叶节点可能会包含多个物理行，叶节点是 B*树的最

后一级。B*树是一种“平衡树”，因为每个叶节点到根节点的距离都

（两个读操作发生在根/分支级，第三个读动作发生在叶节点级）。

需要记住的是，根据索引所布局的方式不同，每个读操作都有可

能是逻辑读或物理读。如果单独的某个读操作将所需要的块放置

在内存中，那么后面的读操作将有可能直接从内存中进行；否则，

它们将需要从硬盘中进行读。高度与阶数成反比，阶数越高，高

度将越低（这种树称为“扁平”树）。在任何B*树的实现中，一个

重要目标就是增加分支数、减少高度，从而保证对叶节点的访问

被加速。

在B *树的实现过程中，主要应该注意的问题是INSERT操作、D

ELETE操作与UPDATE操作。

的关键字）仍然保存在旧叶节点块中。

2)如果新关键字值不是最大的，那么所有的关键字将按照50:50的

比例进行拆分，这时每个叶节点块（旧与新）中将各包含原始叶

节点中的一半关键字。

这个拆分必须通过一个指向新叶节点的新入口向上传送到父节

点。如果父节点已满，那么这个父节点也必须进行拆分，并且需

要将这种拆分向上传送到父节点的父节点。这时，如果这个父节

点也已满，将继续进行这个过程。这样，某个拆分可能最终被一

直传送到根节点。如果根节点满了，根结点也将进行分裂。根结

点在进行分裂的时候，就是树的高度增加的时候。根节点进行分

都有一个 指向下层最左边的块的指针，这样有利于 fast full scan

的快速定位最左边的叶子节点。

每个拆分过程都是要花费一定的开销的，特别是要进行物理硬

盘I/O动作。此外，在进行拆分之前，Oracle必须查找到一个空块，

用来保存这个拆分。可以用以下步骤来进行查找空块的动作：

1) 在索引的自由列表(free-list, 又称为空闲列表) 中查到一个空闲

块，可以通过CREATE/ALTER INDEX命令为一个索引定义多个空闲

列表。索引空闲列表并不能帮助Oracle查找一个可用来存放将要被

插入的新关键字的块。这是因为关键字值不能随机地存放在索引

中可用的第一个“空闲”叶节点块中，这个值必须经过适当的排序之

如果在表空间中没有更多的自由空间，Oracle将产生错误ORA-016

54。

3) 如果通过上述步骤，找到了所需的空闲块，那么这个索引的高

水位标(HWM)将加大。

4) 所找到的空闲块将用来执行拆分动作。

在创建B*树索引时，一个需要注意的问题就是要避免在运行时

进行拆分，或者，要在索引创建过程中进行拆分（“预拆分”），从

而使得在进行拆分时能够快速命中，以便避免运行时插入动作。

当然，这些拆分也不仅仅局限于插入动作，在进行更新的过程中

也有可能会发生拆分动作。

但在索引更新中，如果有关键字发生改变，那么它在树中的位置

也需要发生改变。请记住，一个关键字在B *树中有且只有一个位

置。因此，当某个关键字

发生改变时，关键字的旧表项必须被删除，并且需要在一个新的

叶节点上创建一个新的关键字。旧的表项有可能永远不会被重新

使用，这是因为只有在非常特殊的情况下， Oracle才会重用关键

字表项槽，例如，新插入的关键字正好是被删除的那个关键字

（包括数据类型、长度

等等）。（这里重用的是块，但完全插入相同的值的时候，也不

一定插入在原来的被删除的位置，只是插入在原来的块中，可能

是在大规模删除与更新过程中，表大小不断减小或至少保持不变

但索引不断加大的原因。

通过上面对B *树的分析，可以得出以下的应用准则：

1）避免对那些可能会产生很高的更新动作的列进行索引。

2）避免对那些经常会被删除的表中的多个列进行索引。若有可能，

只对那些在这样的表上会进行删除的主关键字与/或列进行索引。

如果对多个列进行索引是不可避免的，那么就应该考虑根据这些

列对表进行划分，然后在每个这样的划分上执行TRUNCATE动作

（而不是DELETE动作）。TRUNCATE在与DROP STORAGE短语一

4）空值不应该存储在单列索引中。对于复合索引的方式，只有当

某个列不空时，才需要进行值的存储。在为DML语句创建IS NULL

或IS NOT NULL短语时，应该切记这个问题。

5）IS NULL不会导致索引扫描，而一个没有带任何限制的IS NOT

NULL则可能会导致完全索引扫描。

2. PCTFREE的重要性

对于B*树索引， PCTFREE可以决定叶节点拆分的extent。也就

是说，PCTFREE用来说明在某个块中的自由空间数目，以便于后

但是，剩余的20％将用来作为关键字信息后来插入到叶节点块中

时使用。这样将能够保证在需要进行叶节点块的拆分时，运行时

的插入开销最小。虽然一个较高的PCTFREE可能会使得索引创建

时间增加，但它能够防止在实际的使用过程中命中性能的降低。

因此，那些正在等待某个行被插入的终端用户并不会因为需要进

行叶节点块的拆分而使得自己的性能受到影响。

基于上述信息，可以得出以下结论：

1）某个索引的PCTFREE主要是在索引创建时使用。在实际的应用

过程中，PCTFREE将被忽略。

2）如果表是一个经常被访问、包含有大量DML改变（通过交互式

是在表有几百万行时更为如此）。

4）对于任何其值不断增加的列，最好是设置一个非常低的PCTFR

EE（甚至可以为0）。这是因为只有那些最右方的叶节点块总是会

被插入，从而使得树向右增长。而左边的叶节点将一直为静止状

态，因此没有必要使得这些块的任何部分为空（通过使用非零PCT

FREE）。

一、实验索引的物理位置分布以及存储结构

SQL> create table t_test1 as select * from dba_objects where object_id

is not null ;

表已创建。

SQL> create index idx_test_obid on t_test1(object_id) ;

索引已创建。

SQL> select file_id,extent_id,block_id from dba_extents where se

gment_name='IDX_TEST_OBID' ;