从平衡树到oracle b-tree索引的原理探索
先话唠一下，oracle索引，有两类运用较广：
1）b-tree:OLTP（面向交易）
2）bitmap:OLAP（面向分析）
步入正题，先搭建测试环境：
SQL> create table tt as select * from dba_objects;表已创建。SQL> select count(*) from tt; COUNT(*)---------- 50441SQL> insert into tt select * from tt;已创建50441行。SQL> /已创建100882行。SQL> /已创建201764行。SQL> /已创建403528行。SQL> /已创建807056行。SQL> create index tt_index on tt(object_id) tablespace users;索引已创建。
把索引tt_index的结构给dump出来：
SQL> select object_id from dba_objects where object_name='TT_INDEX'; OBJECT_ID---------- 53042SQL> alter session set events 'immediate trace name treedump level 53042';会话已更改。SQL> show parameter user_dump_destNAME TYPE------------------------------------ ----------------------VALUE------------------------------user_dump_dest stringG:\ORACLE\PRODUCT\10.2.0\ADMIN\ORCL\UDUMPSQL> select distinct sid from v$mystat; SID---------- 147SQL> select paddr from v$session where sid=147;PADDR--------CA280DDCSQL> select spid from v$process where addr='CA280DDC';SPID------------------------5360
到udump，把进程号为5360的文件打开，部分内容如下：
*** 2012-08-07 01:21:34.944*** ACTION NAME:() 2012-08-07 01:21:34.902*** MODULE NAME:(SQL*Plus) 2012-08-07 01:21:34.902*** SERVICE NAME:(SYS$USERS) 2012-08-07 01:21:34.902*** SESSION ID:(147.92) 2012-08-07 01:21:34.902----- begin tree dumpbranch: 0x10001bc 16777660 (0: nrow: 7, level: 2) branch: 0x100595f 16800095 (-1: nrow: 578, level: 1) leaf: 0x10001bd 16777661 (-1: nrow: 513 rrow: 513) leaf: 0x10001be 16777662 (0: nrow: 513 rrow: 513) leaf: 0x10001bf 16777663 (1: nrow: 513 rrow: 513) leaf: 0x10001c0 16777664 (2: nrow: 513 rrow: 513) leaf: 0x10001c1 16777665 (3: nrow: 513 rrow: 513) leaf: 0x10001c2 16777666 (4: nrow: 513 rrow: 513) leaf: 0x10001c3 16777667 (5: nrow: 484 rrow: 484) leaf: 0x10001c4 16777668 (6: nrow: 478 rrow: 478) leaf: 0x10001c5 16777669 (7: nrow: 478 rrow: 478) leaf: 0x10001c6 16777670 (8: nrow: 478 rrow: 478) leaf: 0x10001c7 16777671 (9: nrow: 478 rrow: 478) leaf: 0x10001c8 16777672 (10: nrow: 478 rrow: 478) leaf: 0x10001ca 16777674 (11: nrow: 481 rrow: 481) leaf: 0x10001cb 16777675 (12: nrow: 478 rrow: 478) leaf: 0x10001cc 16777676 (13: nrow: 478 rrow: 478) leaf: 0x10001cd 16777677 (14: nrow: 478 rrow: 478) leaf: 0x10001ce 16777678 (15: nrow: 478 rrow: 478) leaf: 0x10001cf 16777679 (16: nrow: 478 rrow: 478)
由此可证明：b-tree中的b是balance，是棵平衡树。否则，一个branch下面只有两个leaf，才是二叉树。
上面：0x10001bd （16进制）和16777661（10进制）这两个，其实，是一样的。
SQL> select to_number('10001bd','xxxxxxx') from dual;TO_NUMBER('10001BD','XXXXXXX')------------------------------ 16777661
而且，16777661包含两部分：文件号、数据块号。意指：这个地址是哪个数据文件上的第几个块
SQL> select dbms_utility.data_block_address_file( 16777661) from dualDBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(16777661)---------------------------------------------- 4SQL> select dbms_utility.data_block_address_block( 16777661) from duaDBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(16777661)----------------------------------------------- 445
由上，可得：4号文件的第445个块
将tt_index的内容给dump出来一下：
SQL> alter system dump datafile 4 block 445;系统已更改。
部分内容摘入如下：
row#0[8024] flag: ------, lock: 0, len=12col 0; len 2; (2): c1 03col 1; len 6; (6): 01 00 01 ac 00 2drow#1[8012] flag: ------, lock: 0, len=12col 0; len 2; (2): c1 03col 1; len 6; (6): 01 00 05 36 00 40row#2[8000] flag: ------, lock: 0, len=12col 0; len 2; (2): c1 03col 1; len 6; (6): 01 00 08 01 00 1brow#3[7988] flag: ------, lock: 0, len=12col 0; len 2; (2): c1 03col 1; len 6; (6): 01 00 0a a2 00 2drow#4[7976] flag: ------, lock: 0, len=12col 0; len 2; (2): c1 03col 1; len 6; (6): 01 00 0d 69 00 48
tt表最小的object_id为2，对应的便是row#0[8024]，那么2在oracle中的16进制是如何存储的呢？
SQL> select dump(2,16) from dual;DUMP(2,16)----------------------------------Typ=2 Len=2: c1,3
由此，可知：2的存储是c1 03.也就是，第0行的第一列存储的值是2.
意味着，在索引的叶子节点里，我们在哪一列上创建索引，其实，oracle就是把该列的值保存到索引的叶子节点里。
索引里第一行第2列16进制数：01 00 01 ac 00 2d和rowid有啥关系呢？
SQL> select object_id,rowid from tt 2 where object_id=2 3 order by object_id,rowid; OBJECT_ID ROWID---------- ------------------ 2 AAAM8xAAEAAAAGsAAt 2 AAAM8xAAEAAAAU2ABA 2 AAAM8xAAEAAAAgBAAb ...
其实，索引里第一行第2列16进制数：01 00 01 ac 00 2d表示的是rowid里面后三部分，也就是：fno、bno、rno。
rowid：AAAM8x AAE AAAAGs AAt。通过进制的转换，AAE AAAAGs AAt和01 00 01 ac 00 2d是一样的。
为什么只有后三个部分呢？说白点，书的目录会把书名给包括进去吗？书名就是对象编号、目录就是索引。
到此，我们把索引的内部结构给构造出来：
object_id rowid(后三部分）
... ...
草图如下：
