B树索引的内部结构

为了观察B树索引的内部结构,首先建立一个实验用的例子:
create table tindex as select * from dba_objects where 1=2;
 
insert into tindex select * from dba_objects;
UPDATE TINDEX SET OBJECT_NAME=ROWNUM;
commit;
DROP INDEX TST_IDX;
create index tst_idx on tindex (object_name);
然后在SYS用户下,使用下面的脚本找到索引所在的块号,并把前面的3块导出:
SQL> COL SEGMENT_NAME FORMAT A30 TRUNCATE;
SQL> select segment_name,extent_id,file_id,block_id
  2  from dba_extents  where segment_name = 'TST_IDX' AND WNER='TEST';
 
SEGMENT_NAME             EXTENT_ID    FILE_ID   BLOCK_ID
------------------------------ ---------- ---------- ----------
TST_IDX                                 0         10      20097
TST_IDX                                 1         10      20249
TST_IDX                                 2         10      20281
TST_IDX                                 3         10      20313
TST_IDX                                 4         10      20345
TST_IDX                                 5         10      20377
TST_IDX                                 6         10      20393
TST_IDX                                 7         10      20401
TST_IDX                                 8         10      20409
TST_IDX                                 9         10      20417
 
已选择10行。
alter system dump datafile 10 block 20097;
alter system dump datafile 10 block 20098;
alter system dump datafile 10 block 20099;
其中,20097是段头的信息,我们就不进行详细的分析了。20098是整个索引的根,列出部分重要的信息,然后我们来进行分析:
Start dump data blocks tsn: 10 file#: 10 minblk 20098 maxblk 20098
buffer tsn: 10 rdba: 0x02804e82 (10/20098)
scn: 0x0000.0025f32c seq: 0x01 flg: 0x00 tail: 0xf32c0601
frmt: 0x02 chkval: 0x0000 type: 0x06=trans data –块的类型是数据块
Block header dump:  0x02804e82
 Object id on Block? Y
 seg/obj: 0x91a9  csc: 0x00.25f31f  itc: 1  flg: -  typ: 2 – INDEX –对象的类别是索引
     fsl: 0  fnx: 0x0 ver: 0x01
 --下面是事务槽的情况
 Itl           Xid                  Uba         Flag  Lck        Scn/Fsc
0x01   0xffff.000.00000000  0x00000000.0000.00  C---    0  scn 0x0000.0025f31f
 
Branch block dump
=================
header address 139726916=0x8541044
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: pcode=0: iot flags=--- is converted=Y
kdxconco 2 –列数为2,说明有一个键值
kdxcosdc 0
kdxconro 76 –根节点有76条记录
kdxcofbo 180=0xb4
kdxcofeo 7246=0x1c4e
kdxcoavs 7066
kdxbrlmc 41963139=0x2804e83  --第一个叶节点的地址(存放最小的键值的数据)
kdxbrsno 0
kdxbrbksz 8060
row#0[8049] dba: 41963140=0x2804e84 ----第一个键值索引的下级块地址,该地址包含的是大于等于第一个键值的第一个下级节点的地址
col 0; len 5; (5):  31 30 33 38 30  ----第一个键值范围10380
col 1; TERM
row#1[8038] dba: 41963141=0x2804e85
col 0; len 5; (5):  31 30 37 36 33 ----第二个键值范围10763
col 1; TERM
从上面的数据可以看出,第一个叶节点是0X02804E83,存放最小键值开始的数据。“10380”以上键值的记录的下一级节点是0X02804E84(20100),以下是该节点的数据:
buffer tsn: 10 rdba: 0x02804e84 (10/20100)
……
Leaf block dump
===============
header address 139726940=0x854105c
kdxcolev 0
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: pcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 425
kdxcofbo 886=0x376
kdxcofeo 1707=0x6ab
kdxcoavs 821
kdxlespl 0
kdxlende 0
kdxlenxt 41963141=0x2804e85  --下一个叶节点的地址
kdxleprv 41963139=0x2804e83  --前一个叶节点的地址
kdxledsz 0
kdxlebksz 8036
row#0[8021] flag: -----, lock: 0  --第一条记录
col 0; len 5; (5):  31 30 33 38 30  --键值是10380
col 1; len 6; (6):  02 80 50 13 00 19  --表中记录的地址(RDBA)是0x02805013(10/20499),第19条记录
row#1[8006] flag: -----, lock: 0
col 0; len 5; (5):  31 30 33 38 31
col 1; len 6; (6):  02 80 50 13 00 1a
row#2[7991] flag: -----, lock: 0
col 0; len 5; (5):  31 30 33 38 32
col 1; len 6; (6):  02 80 50 13 00 1b
row#3[7976] flag: -----, lock: 0
col 0; len 5; (5):  31 30 33 38 33
col 1; len 6; (6):  02 80 50 13 00 1c
row#4[7961] flag: -----, lock: 0
col 0; len 5; (5):  31 30 33 38 34
col 1; len 6; (6):  02 80 50 13 00 1d
row#5[7946] flag: -----, lock: 0
col 0; len 5; (5):  31 30 33 38 35
col 1; len 6; (6):  02 80 50 13 00 1e
….
….
row#423[1722] flag: -----, lock: 0
col 0; len 5; (5):  31 30 37 36 31
col 1; len 6; (6):  02 80 50 18 00 2d
row#424[1707] flag: -----, lock: 0
col 0; len 5; (5):  31 30 37 36 32
col 1; len 6; (6):  02 80 50 18 00 2e
----- end of leaf block dump -----
End dump data blocks tsn: 10 file#: 10 minblk 20100 maxblk 20100
可以看出这个节点是叶节点,其中有一个叶节点链表的信息十分重要:
kdxlenxt 41963141=0x2804e85  --下一个叶节点的地址
kdxleprv 41963139=0x2804e83  --前一个叶节点的地址
这个节点中,每条记录直接存储了键值对应的表的地址。看第一条记录:
row#0[8021] flag: -----, lock: 0  --第一条记录
col 0; len 5; (5):  31 30 33 38 30  --键值是10380
col 1; len 6; (6):  02 80 50 13 00 19  --表中记录的地址(RDBA)是0x02805013(10/20499),第25号记录
下面来核对10号文件中的20499块的第25号记录:
ALTER SYSTEM DUMP DATAFILE 10 BLOCK 20499;
我们略过其他信息,直接查看25号记录的信息:
tab 0, row 25, @0x179b
tl: 79 fb: --H-FL-- lb: 0x2  cc: 13
col  0: [ 3]  53 59 53 – ascii码:SYS
col  1: [ 5]  31 30 33 38 30  --ascii码:10380
col  2: *NULL*
col  3: [ 4]  c3 02 19 5f  --number类型数据:12494
col  4: *NULL*
col  5: [10]  4a 41 56 41 20 43 4c 41 53 53
col  6: [ 7]  78 68 06 1b 0f 1b 18
col  7: [ 7]  78 68 06 1b 0f 1b 18
col  8: [19]  32 30 30 34 2d 30 36 2d 32 37 3a 31 34 3a 32 36 3a 32 33
col  9: [ 5]  56 41 4c 49 44
col 10: [ 1]  4e
col 11: [ 1]  4e
col 12: [ 1]  4e

通过下面的查询可以验证索引的结果:
SQL> select owner,object_name,object_id from tindex where object_name='10380';
 
OWNER   OBJECT_NAME  OBJECT_ID
------------------------------------------------------------------------------
SYS       10380           12494
和DUMP出来的数据完全一致。
请使用浏览器的分享功能分享到微信等