第11章 索引
索引是应用设计和开发的一个重要方面。如果有太多的索引，DML的性能就会受到影响。如果索引太少，又会影响查询（包括插入、更新和删除）的性能。要找到一个合适的平衡点，这对于应用的性能至关重要。
我常常发现，人们在应用开发中总是事后才想起索引。我坚持认为这是一种错误的做法。如果你知道数据将如何使用，从一开始就应该能提出应用中要使用怎样的索引，即具有一组代表性的索引。不过，一般的做法却往往是随应用“放任自流“，过后才发现哪里需要索引，这种情况实在太多了。这说明，你没有花时间来了解数据将如何使用以及最终要处理多少行。经过一段时间后，随着数据量的增长，你会不停地向系统增加索引（也就是说，你所执行的是一种反应式调优）。你就有一些冗余而且从不使用的索引，这不仅会浪费空间，还会浪费计算资源。磨刀不误砍柴工，如果刚开始的时候花几个小时好好地考虑何时为数据加索引，以及如何加索引，这肯定能在以后的”调优“中节省更多的时间（注意，我所说的是”肯定能“节省更多时间，而不只是”可能“节省更多时间）。
这一章的主旨是对Oracle中可用的索引提供一个概述，讨论什么时候以及在哪里可以使用索引。这一章的风格和格式与本书其他章有所不同。索引是一个很宽泛的主题，光是介绍索引就可以单独写一本书，其部分原因是：索引是开发人员和DBA角色之间的一个桥梁。一方面，开发人员必须了解索引，清楚如何在应用中使用索引，而且知道何时使用索引（以及何时不使用索引）等。另一方面，DBA则要考虑索引的增长、索引中存储空间的使用以及其他物理特性。我们将主要从应用角度来考虑，也就是从索引的实际使用来介绍索引。这一章前半部分提供了一些基本知识。这一章的后半部分回答了关于索引的一些最常问到的问题。
这一章中的各个例子分别需要不同的Oracle版本中的特性。如果每个例子需要Oracle企业版或个人版的某些特性（而标准版中不支持），我会明确地指出来。
11.1 Oracle索引概述
Oracle提供了多种不同类型的索引以供使用。简单地说，Oracle中包括如下索引：
B*树索引：这些是我所说的“传统“索引。到目前为止，这是Oracle和大多数其他数据库中最常用的索引。B*树的构造类似于二叉树，能根据键提供一行或一个行集的快速访问，通常只需很少的读操作就能找到正确的行。不过，需要注意重要的一点，”B*树“中的”B“不代表二叉（binary），而代表平衡（balanced）。B*树索引并不是一颗二叉树，这一点在介绍如何在磁盘上物理地存储B*树时就会了解到。B*树索引有以下子类型：
索引组织表（index organized table）：索引组织表以B*树结构存储。堆表的数据行是以一种无组织的方式存储的（只要有可用的空间，就可以放数据），而IOT与之不同，IOT中的数据要按主键的顺序存储和排序。对应用来说，IOT表现得与“常规“表并无二致；需要使用SQL来正确地访问IOT。IOT对信息获取、空间系统和OLAP应用最为有用。IOT在上一章已经详细地讨论过。
B*树聚簇索引（B*tree cluster index）这些是传统B*树索引的一个变体（只是稍有变化）。B*树聚簇索引用于对聚簇键建立索引（见第11.章中“索引聚簇表“一节），所以这一章不再讨论。在传统B*树中，键都指向一行；而B*树聚簇不同，一个聚簇键会指向一个块，其中包含与这个聚簇键相关的多行。
降序索引（descending index）：降序索引允许数据在索引结构中按“从大到小“的顺序（降序）排序，而不是按”从小到大“的顺序（升序）排序。我们会解释为什么降序索引很重要，并说明降序索引如何工作。
反向键索引（reverse key index）：这也是B*树索引，只不过键中的字节会“反转“。利用反向键索引，如果索引中填充的是递增的值，索引条目在索引中可以得到更均匀的分布。例如，如果使用一个序列来生成主键，这个序列将生成诸如987500、987501、987502等值。这些值是顺序的，所以倘若使用一个传统的B*树索引，这些值就可能放在同一个右侧块上，这就加剧了对这一块的竞争。利用反向键，Oracle则会逻辑地对205789、105789、005789等建立索引。Oracle将数据放在索引中之前，将先把所存储数据的字节反转，这样原来可能在索引中相邻放置的值在字节反转之后就会相距很远。通过反转字节，对索引的插入就会分布到多个块上。
位图索引（bitmap index）：在一颗B*树中，通常索引条目和行之间存在一种一对一的关系：一个索引条目就指向一行。而对于位图索引，一个索引条目则使用一个位图同时指向多行。位图索引适用于高度重复而且通常只读的数据（高度重复是指相对于表中的总行数，数据只有很少的几个不同值）。考虑在一个有100万行的表中，每个列只有3个可取值：Y、N和NULL。举例来说，如果你需要频繁地统计多少行有值Y，这就很适合建立位图索引。不过并不是说如果这个表中某一列有11.000个不同的值就不能建立位图索引，这一列当然也可以建立位图索引。在一个OLTP数据库中，由于存在并发性相关的问题，所以不能考虑使用位图索引（后面我们就会讨论这一点）。注意，位图索引要求使用Oracle企业版或个人版。
位图联结索引（bitmap join index）：这为索引结构（而不是表）中的数据提供了一种逆规范化的方法。例如，请考虑简单的EMP和DEPT表。有人可能会问这样一个问题：“多少人在位于波士顿的部门工作？“EMP有一个指向DEPT的外键，要想统计LOC值为Boston的部门中的员工人数，通常必须完成表联结，将LOC列联结至EMP记录来回答这个问题。通过使用位图联结索引，则可以在EMP表上对LOC列建立索引。
基于函数的索引（function-based index）：这些就是B*树索引或位图索引，它将一个函数计算得到的结果存储在行的列中，而不是存储列数据本身。可以把基于函数的索引看作一个虚拟列（或派生列）上的索引，换句话说，这个列并不物理存储在表中。基于函数的索引可以用于加快形如SELECT * FROM T WHERE FUNCTION(DATABASE_COLUMN) = SAME_VALUE这样的查询，因为值FUNCTION(DATABASE_COLUMN)已经提前计算并存储在索引中。
应用域索引（application domain index）：应用域索引是你自己构建和存储的索引，可能存储在Oracle中，也可能在Oracle之外。你要告诉优化器索引的选择性如何，以及执行的开销有多大，优化器则会根据你提供的信息来决定是否使用你的索引。Oracle文本索引就是应用域索引的一个例子；你也可以使用构建Oracle文本索引所用的工具来建立自己的索引。需要指出，这里创建的“索引“不需要使用传统的索引结构。例如，Oracle文本索引就使用了一组表来实现其索引概念。
可以看到，可供选择的索引类型有很多。在下面几节中，我将提供有关的一些技术细节来说明某种索引如何工作，以及应该何时使用这些索引。需要重申一遍，在此不会涵盖某些与DBA相关的主题。例如，我们不打算讨论在线重建索引的原理；而会把重点放在与应用相关的实用细节上。
11.2 B*树索引
B*树索引就是我所说的“传统“索引，这是数据库中最常用的一类索引结构。其实现与二叉查找树很相似。其目标是尽可能减少Oracle查找数据所花费的时间。不严格地说，如果在一个数字列上有一个索引，那么从概念上讲这个结构可能如图11.-1所示。
注意 也许会有一些块级优化和数据压缩，这些可能会使实际的块结构与图11.-1所示并不同。
图11.-1 典型的B*树索引布局
这个树最底层的块称为叶子节点（leaf node）或叶子块（leaf block），其中分别包含各个索引键以及一个rowid（指向所索引的行）。叶子节点之上的内部块称为分支块（branch block）。这些节点用于在结构中实现导航。例如，如果想在索引中找到值42，要从树顶开始，找到左分支。我们要检查这个块，并发现需要找到范围在“42..50“的块。这个块将是叶子块，其中会指示包含数42的行。有意思的是，索引的叶子节点实际上构成了一个双向链表。一旦发现要从叶子节点中的哪里”开始“（也就是说，一旦发现第一个值），执行值的有序扫描（也称为索引区间扫描（index range scan））就会很容易。我们不用再在索引结构中导航；而只需根据需要通过叶子节点向前或向后扫描就可以了。所以要满足诸如以下的谓词条件将相当简单：
|
where x between 20 and 30 |
Oracle发现第一个最小键值大于或等于20的索引叶子块，然后水平地遍历叶子节点链表，直到最后命中一个大于30的值。
B*树索引中不存在非惟一（nonunique）条目。在一个非惟一索引中，Oracle会把rowid作为一个额外的列（有一个长度字节）追加到键上，使得键惟一。例如，如果有一个CREATE INDEX I ON T(X,Y)索引，从概念上讲，它就是CREATE UNIQUE INDEX I ON T(X,Y,ROWID)。在一个惟一索引中，根据你定义的惟一性，Oracle不会再向索引键增加rowid。在非惟一索引中，你会发现，数据会首先按索引键值排序（依索引键的顺序）。然后按rowid升序排序。而在惟一索引中，数据只按索引键排序。
B*树的特点之一是：所有叶子块都应该在树的同一层上。这一层也称为索引的高度（height），这说明所有从索引的根块到叶子块的遍历都会访问同样数目的块。也就是说，对于形如”SELECT INDEXED_COL FROM T WHERE INDEXED_COL = :X“的索引，要到达叶子块来获取第一行，不论使用的:X值是什么，都会执行同样数目的I/O。换句话说，索引是高度平衡的（height balanced）。大多数B*树索引的高度都是2或者3，即使索引中有数百万行记录也是如此。这说明，一般来讲，在索引中找到一个键只需要执行2或3次I/O，这倒不坏。
注意 Oracle在表示从索引根块到叶子块遍历所涉及的块数时用了两个含义稍有不同的术语。第一个是高度（HEIGHT），这是指从根块到叶子块遍历所需的块数。使用ANALYZE INDEX <name> VALIDATE STRUCTURE命令分析索引后，可以从INDEX_STATS视图找到这个高度（HEIGHT）值。另一个术语是BLEVEL，这是指分支层数，与HEIGHT相差1（BLEVEL不把叶子块层算在内）。收集统计信息后，可以在诸如USER_INDEXES之类的常规字典表中找到BLEVEL值。
例如，假设有一个11.,000,000行的表，其主键索引建立在一个数字列上：
|
big_table@ORA9IR2> select index_name, blevel, num_rows 2 from user_indexes 3 where table_name = 'BIG_TABLE'; INDEX_NAME BLEVEL NUM_ROWS ------------------------------ ---------- ---------- BIG_TABLE_PK 2 10441513 |
BLEVEL为2，这说明HEIGHT为3，要找到叶子需要两个I/O（访问叶子本身还需要第三个I/O）。所以，要从这个索引中获取任何给定的键值，共需要3个I/O：
|
big_table@ORA9IR2> select id from big_table where id = 42; Execution Plan ---------------------------------------------------------- 0 SELECT STATEMENT Optimizer=CHOOSE (Cost=2 Card=11.Bytes=6) 11.0 INDEX (UNIQUE SCAN) OF 'BIG_TABLE_PK' (UNIQUE) (Cost=2 Card=11.Bytes=6) Statistics ---------------------------------------------------------- ... 3 consistent gets ... 11.rows processed big_table@ORA9IR2> select id from big_table where id = 12345; Statistics ---------------------------------------------------------- ... 3 consistent gets ... 11.rows processed big_table@ORA9IR2> select id from big_table where id = 1234567; Statistics ---------------------------------------------------------- ... 3 consistent gets ... 11.rows processed |
B*树是一个绝佳的通用索引机制，无论是大表还是小表都很适用，随着底层表大小的增长，获取数据的性能只会稍有恶化（或者根本不会恶化）。
11.2.1 索引键压缩
对于B*树索引，可以做的一件有意思的工作是“压缩”。这与压缩ZIP文件的方式不同，它是指从串联（多列）索引去除冗余。
在第11.章的“索引组织表”一节中我们曾经详细地讨论压缩键索引，这里再简要地做个说明。压缩键索引（compressed key index）的基本概念是，每个键条目分解为两个部分：“前缀”和“后缀”。前缀建立在串联索引（concatenated index）的前几列上，这些列有许多重复的值。后缀则在索引键的后几列上，这是前缀所在索引条目中的惟一部分（即有区别的部分）。
下面通过一个例子来说明，我们将创建一个表和一个串联索引，并使用ANALYZE INDEX测量无压缩时所用的空间。然后利用索引压缩创建这个索引，分别压缩不同数目的键条目，查看有什么差别。下面先来看这个表和索引：
|
ops$tkyte@ORA 2 as 3 select * from all_objects; Table created.
ops$tkyte@ORA 2 t(owner,object_type,object_name); Index created.
ops$tkyte@ORA Index analyzed. |
然后创建一个INX_STATS表，在这里存放INDEX_STATS信息，我们把表中的行标记为“未压缩”（noncompressed）：
|
ops$tkyte@ORA 2 as 3 select 'noncompressed' what, a.* 4 from index_stats a; Table created. |
现在可以看到，OWNER部分重复了多次，这说明，这个索引中的一个索引块可能有数十个条目，如图11.-2所示。
图11.-2 有重复OWNER列的索引块
可以从中抽取出重复的OWNER列，这会得到如同11.-3所示的块。
图11.-3 抽取了OWNER列的索引块
在图11.-3中，所有者（owner）名在叶子块上只出现了一次，而不是在每个重复的条目上都出现一次。运行以上脚本，传入数字1作为参数来重新创建这个索引，在此索引使用了第一列的压缩：
|
drop index t_idx; create index t_idx on t(owner,object_type,object_name) compress &1; analyze index t_idx validate structure; insert into idx_stats select 'compress &1', a.* from index_stats a; |
为了进行比较，我们不仅在压缩一列的基础上运行了这个脚本，还分别使用了两个和3个压缩列来运行这个脚本，查看会发生什么情况。最终，我们将查询IDX_STATS，应该能观察到以下信息：
|
ops$tkyte@ORA 2 btree_space, opt_cmpr_count, opt_cmpr_pctsave 3 from idx_stats 4 / WHAT HEIGHT LF_BLKS BR_BLKS BTREE_SPACE OPT_CMPR_COUNT OPT_CMPR_PCTSAVE ------------- ------- -------- ------- ----------- -------------- ---------------- noncompressed 3 337 3 2718736 2 28 compress 1 3 300 3 2421684 2 11. compress 2 2 240 1 1926108 2 0 compress 3 3 375 3 3021084 2 35 |
可以看到，COMPRESS 1索引的大小大约是无压缩索引的89%（通过比较BTREE_SPACE得出）。叶子块数大幅度下降。更进一步，使用COMPRESS 2时，节省的幅度更为显著。所得到的索引大约是原索引（无压缩索引）的70%，而且由于数据量减少，这些数据能放在单个块上，相应地索引的高度就从3降为2.实际上，利用列OPT_CMPR_PCTSAVE的信息（这代表最优的节省压缩百分比（optimum compression percent saved）或期望从压缩得到的节省幅度）。我们可以猜测出COMPRESS 2索引的大小：
|
ops$tkyte@ORA
2718736*(11.0.28) ---------------- 1957489.92 |
注意 对无压缩索引执行ANALYZE命令时，会填写OPT_CMPR_PCTSAVE/OPT_CMPR_COUNT列，并估计出：利用COMPRESS 2，可以节省28%的空间；而事实确实如此，我们果真节省了大约这么多的空间。
不过，再看看COMPRESS 3会怎么样。如果压缩3列，所得到的索引实际上会更大：是原来索引大小的110%。这是因为：每删除一个重复的前缀，能节省N个副本的空间，但是作为压缩机制的一部分，这会在叶子块上增加4字节的开销。把OBJECT_NAME列增加到压缩键后，则使得这个键是惟一的；在这种情况下，则说明没有重复的副本可以提取。因此，最后的结果就是：我们只是向每个索引键条目增加了4个字节，而不能提取出任何重复的数据。IDX_STATS中的OPT_CMPR_COUNT列真是精准无比，确实给出了可用的最佳压缩数，OPT_COMPR_PCTSAVE则指出了可以得到多大的节省幅度。
对现在来说，这种压缩不是免费的。现在压缩索引比原来更复杂了。Oracle会花更多的时间来处理这个索引结构中的数据，不光在修改期间维护索引更耗时，查询期间搜索索引也更花时间。利用压缩，块缓冲区缓存比以前能存放更多的索引条目，缓冲命中率可能会上升，物理I/O应该下降，但是要多占用一些CPU时间来处理索引，还会增加块竞争的可能性。在讨论散列聚簇时，我们曾经说过，对于散列聚簇，获取100万个随机的行可能占用更多的CPU时间，但是I/O数会减半；这里也是一样，我们必须清楚存在的这种折中。如果你现在已经在大量占用CPU时间，在增加压缩键索引只能适得其反，这会减慢处理的速度。另一方面，如果目前的I/O操作很多，使用压缩键索引就能加快处理速度。
11.2.2 反向键索引
B*树索引的另一个特点是能够将索引键“反转”。首先，你可以问问自己“为什么想这么做？” B*树索引是为特定的环境、特定的问题而设计的。实现B*树索引的目的是为了减少“右侧”索引中对索引叶子块的竞争，比如在一个Oracle RAC环境中，某些列用一个序列值或时间戳填充，这些列上建立的索引就属于“右侧”（right-hand-side）索引。
注意 我们在第2章讨论过RAC。
RAC是一种Oracle配置，其中多个实例可以装载和打开同一个数据库。如果两个实例需要同时修改同一个数据块，它们会通过一个硬件互连（interconnect）来回传递这个块来实现共享，互连是两个（或多个）机器之间的一条专用网络连接。如果某个利用一个序列填充，这个列上有一个主键索引（这是一种非常流行的实现），那么每个人插入新值时，都会视图修改目前索引结构右侧的左块（见图11.-1，其中显示出索引中较高的值都放在右侧，而较低的值放在左侧）。如果对用序列填充的列上的索引进行修改，就会聚集在很少的一组叶子块上。倘若将索引的键反转，对索引进行插入时，就能在索引中的所有叶子键上分布开（不过这往往会使索引不能得到充分地填充）。
注意 你可能还会注意到，反向键可以用作一种减少竞争的方法（即使只有一个Oracle实例）。不过重申一遍，如这一节所述，反向键主要用于缓解忙索引右侧的缓冲区忙等待。
在介绍如何度量反向键索引的影响之前，我们先来讨论物理上反向键索引会做什么。反向键索引只是将索引键中各个列的字节反转。如果考虑90101、90102和90103这样几个数，使用Oracle DUMP函数查看其内部表示，可以看到这几个数的表示如下：
|
ops$tkyte@ORA10GR1> select 90101, dump(90101,11.) from dual 2 union all 3 select 90102, dump(90102,11.) from dual 4 union all 5 select 90103, dump(90103,11.) from dual 6 /
90101 DUMP(90101,11.) ---------- --------------------- 90101 Typ=2 Len=4: c3,a,2,2 90102 Typ=2 Len=4: c3,a,2,3 90103 Typ=2 Len=4: c3,a,2,4 |
每个数的长度都是4字节，它们只是最后一个字节有所不同。这些数最后可能在一个索引结构中向右依次放置。不过，如果反转这些数的字节，Oracle就会插入以下值：
|
ops$tkyte@ORA10GR1> select 90101, dump(reverse(90101),11.) from dual 2 union all 3 select 90102, dump(reverse(90102),11.) from dual 4 union all |