B*树索引是Oracle的“传统“索引。
B*树的构造类似于二叉树，能根据键提供一行或一个行集的快速访问，通常只需很少的读操作就能找到正确的行。
不过，”B*树“中的”B“不代表二叉（binary），而代表平衡（balanced）。B*树索引并不是一颗二叉树。在一个数字列上建立的索引类似于下图:
叶子节点之上的内部块称为分支块（branch block）。这些节点用于在结构中实现导航。
最底层的块称为叶子节点（leaf node）或叶子块（leaf block），其中分别包含各个索引键以及一个rowid（指向所索引的行）。
索引的叶子节点实际上构成了一个双向链表，这样有利于执行索引区间扫描（index range scan）以满足类似"where x between 20 and 30"的查询。
所有叶子块都在树的同一层上，从索引的根块到叶子块的遍历都会访问同样数目的块。这一层也称为索引的高度（height）。大多数B*树索引的高度都是2或者3。
另一个术语是BLEVEL，这是指分支层数，与HEIGHT相差1（BLEVEL不把叶子块层算在内）。
B*树索引有以下子类型：
1）索引组织表（index organized table）
索引组织表以B*树结构存储。
http://blog.****.net/fw0124/article/details/6902006
2）B*树聚簇索引（B*tree cluster index）
在传统B*树索引中，键都指向一行；而B*树聚簇索引不同，一个聚簇键会指向一个块，其中包含与这个聚簇键相关的多行。
http://blog.****.net/fw0124/article/details/6902048
3）反向键索引（reverse key index）
键中的字节会“反转“。利用反向键索引，如果索引中填充的是递增的值，索引条目在索引中可以得到更均匀的分布。
例如，如果使用一个序列来生成主键，这些键值将会是顺序的，那么每个人插入新值时，都会修改目前索引结构右侧的块，这就加剧了对这一块的竞争。
利用反向键，Oracle将数据放在索引中之前，将先把所存储数据的字节反转，这样对索引的插入就会分布到多个块上。
但是在进行类似"where x > 5"的查询时，X上的反向键索引就没有作用。
使用关键字REVERSE来创建反向键索引。例如：
create table t(id int primary key using index reverse);
4）降序索引（descending index）
降序索引允许数据在索引结构中按“从大到小“的顺序（降序）排序，而不是按”从小到大“的顺序（升序）排序。
为什么需要降序索引？下面的例子可以说明。
[email protected]> create table t as select * from all_objects;
Table created.
[email protected]> create index t_idx on t(owner,object_type,object_name);
Index created.
[email protected]> exec dbms_stats.gather_table_stats( user, 'T');
PL/SQL procedure successfully completed.
[email protected]> set autotrace traceonly explain
[email protected]> select owner, object_type, object_name from t
2 where owner between 'T' and 'Z'
3 and object_type is not null
4 order by owner DESC, object_type DESC;
Execution Plan
----------------------------------------------------------
Plan hash value: 2685572958
-------------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 13838 | 567K| 102 (0)| 00:00:02 |
|* 1 | INDEX RANGE SCAN DESCENDING| T_IDX | 13838 | 567K| 102 (0)| 00:00:02 |
-------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("OWNER">='T' AND "OWNER"<='Z')
filter("OBJECT_TYPE" IS NOT NULL)
Oracle会向前读索引,所以查询计划中没有排序。
但是如果有一些列按升序排列，一些列按降序排列，会有不同，如下：
[email protected]> select owner, object_type, object_name from t
2 where owner between 'T' and 'Z'
3 and object_type is not null
4 order by owner DESC, object_type ASC;
Execution Plan
----------------------------------------------------------
Plan hash value: 2813023843
-----------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes |TempSpc| Cost (%CPU)| Time |
-----------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 13838 | 567K| | 255 (1)| 00:00:04 |
| 1 | SORT ORDER BY | | 13838 | 567K| 720K| 255 (1)| 00:00:04 |
|* 2 | INDEX RANGE SCAN| T_IDX | 13838 | 567K| | 102 (0)| 00:00:02 |
-----------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access("OWNER">='T' AND "OWNER"<='Z')
filter("OBJECT_TYPE" IS NOT NULL)
可以看到现在必须执行排序操作。
但是如果改用降序索引（使用DESC关键字），有如下结果，可以看到现在不需要排序操作了。
[email protected]> drop index desc_t_idx;
Index dropped.
[email protected]> create index desc_t_idx on t(owner desc,object_type,object_name);
Index created.
[email protected]> select owner, object_type, object_name from t
2 where owner between 'T' and 'Z'
3 and object_type is not null
4 order by owner DESC, object_type ASC;
Execution Plan
----------------------------------------------------------
Plan hash value: 2494308350
-------------------------------------------------------------------------------
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time |
-------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 13838 | 567K| 4 (0)| 00:00:01 |
|* 1 | INDEX RANGE SCAN| DESC_T_IDX | 13838 | 567K| 4 (0)| 00:00:01 |
-------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access(SYS_OP_DESCEND("OWNER")>=HEXTORAW('A5FF') AND
SYS_OP_DESCEND("OWNER")<=HEXTORAW('ABFF') )
filter(SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))>='T' AND
SYS_OP_UNDESCEND(SYS_OP_DESCEND("OWNER"))<='Z' AND "OBJECT_TYPE" IS NOT
NULL)
