浅析Oracle b-tree index搜索原理

索引与表一样，也属于段（segment）的一种。里面存放了用户的数据，跟表一样需要占用磁盘空间。只不过，在索引里的数据存放形式与表里的数据存放形式非常的不一样。在理解索引时，可以想象一本书，其中书的内容就相当于表里的数据，而书前面的目录就相当于该表的索引。同时，通常情况下，索引所占用的磁盘空间要比表要小的多，其主要作用是为了加快对数据的搜索速度。

但是，索引作为一种可选的数据结构，你可以选择为某个表里的创建索引，也可以不创建。这是因为一旦创建了索引，就意味着Oracle对表进行DML（包括INSERT、UPDATE、DELETE）时，必须处理额外的工作量（也就是对索引结构的维护）以及存储方面的开销。所以创建索引时，需要考虑创建索引所带来的查询性能方面的提高，与引起的额外的开销相比，是否值得。

B树索引是一个典型的树结构，始终是平衡的，也就是说 从Root节点到 Leaf 节点的任何一个路径都是等距离的。其包含的组件主要是：

叶子节点（Leaf node）：包含条目直接指向表里的数据行。

分支节点（Branch node）：包含的条目指向索引里其他的分支节点或者是叶子节点。

根节点（Branch node）：一个B树索引只有一个根节点，它实际就是位于树的最顶端的分支节点。

对于分支节点块（包括根节点块）来说，其所包含的索引条目都是按照顺序排列的（可以指定reverse，倒序）。每个索引条目（也可以叫做每条记录）都具有两个字段。第一个字段表示当前该分支节点块下面所链接的索引块中所包含的最小键值（按B+tree最小键值复制原则）；第二个字段为四个字节，表示所链接的索引块的地址，该地址指向下面一个索引块。在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。

对于叶子节点块来说，其所包含的索引条目与分支节点一样，都是按照顺序排列的（缺省是升序排列，也可以在创建索引时指定为降序排列）。每个索引条目（也可以叫做每条记录）也具有两个字段。第一个字段表示索引的键值，对于单列索引来说是一个值；而对于多列索引来说则是多个值组合在一起的。第二个字段表示键值所对应的记录行的ROWID，该ROWID是记录行在表里的物理地址。在叶子节点中，每个索引条目都会在数据块中占一行空间。每一行用2到3个字节作为行头，行头用来存放标记以及锁定类型等信息。同时，在第一个表示索引的键值的字段中，每一个索引列都有1个字节表示数据长度，后面则是该列具体的值。

下面分别把分支节点的索引结构和叶子节点的索引信息dump出来

创建测试数据

1. sys@ORCL> select * from v$version where rownum=1;  
2.   
3. BANNER  
4. ----------------------------------------------------------------   
5. Oracle Database 10g Enterprise Edition Release 10.2.0.1.0 - Prod  
6.   
7. sys@ORCL> drop table tt purge;  
8. drop table tt purge  
9.            *  
10. ERROR at line 1:  
11. ORA-00942: table or view does not exist  
12.   
13.   
14. sys@ORCL> create table tt as select * from dba_objects;  
15.   
16. Table created.  
17.   
18. sys@ORCL> select count(*) from tt;  
19.   
20.   COUNT(*)  
21. ----------   
22.      50356  
23.   
24. sys@ORCL> insert into tt select * from tt;  
25.   
26. 50356 rows created.  
27.   
28. sys@ORCL> commit;  
29.   
30. Commit complete.  
31.   
32. sys@ORCL> select count(*) from tt;  
33.   
34.   COUNT(*)  
35. ----------   
36.     100712  
37.   
38. sys@ORCL> create index btree_tt on tt(object_name);  
39.   
40. Index created.