oracle B*树索引

        B*树索引是最常用的数据库索引，一般所说的索引都是B*树索引

        B*树索引的构造类似于二叉树，能根据键提供一行或一个行集的快速访问，通常只需要很少的读操作就能找到正确的行。

        B*树索引的结构有可能如下图所示

 

        这个树最底层的块称为叶子节点(leaf node)或叶子块(leaf block),其中分别包含各个索引建以及一个rowid(指向所索引的行)。叶子节点之上的内部块称为分支块(branch block)。这些节点用于在结构中实现导航。

有意思的是，索引的叶子节点实际上又构成了一个双向链表，执行索引区间扫描(值的有序扫描)也很容易，找到第一个值之后，我们不需要再在索引结构中导航，而只需根据需要，通过叶子节点向前或向后扫描就可以了。所以要满足诸如以下的谓词条件将相当简单：
  where x between 20 and 30
Oracle发现第一个最小值大于或等于20的索引叶子块，然后水平地遍历叶子节点链表，直到命中一个大于30的值。

        B*树索引中不存在非唯一(nonunique)条目。在一个非唯一索引中，Oracle会把rowid作为一个额外的列追加到键上，使得键唯一。在一个唯一索引中，根据你定义的唯一性，Oracle不会再向索引建增加rowid。

        所有叶子块都应该在树的同一个层上，这一层的层号就称为索引的高度，这表示所有从索引的根块到叶子块的遍历都会访问同样数目的块。即索引是高度平衡的，大多数的B*树索引高度都是2或者3，即使索引中有数百万行记录，所以一般来说，在索引中找到一个键只需要执行2或3次I/O。随着基表的增长，通过索引访问数据的性能基本上不会有太大的恶化，因为只要索引高度不变化，读索引的I/O是相同的。而通过rowid访问数据行的效率也是相同，性能仅根据返回的数据量而变化。