首页 > 代码库 > 理解 B*tree index内部结构
理解 B*tree index内部结构
转载请注明出处：http://write.blog.csdn.net/postedit/40589651
Oracle数据库里的B树索引就好象一棵倒长的树，它包含两种类型的数据块：一种是索引分支块，另一种是索引叶子块 索引分支块包含指向相应索引分支块/叶子块的指针和索引健值列（这里的指针是指相关分支块/叶子块的块地址RDBA。
每个索引分支块都会有两种类型的指针，一种是LMC,另一种就索引分支的索引行记录所记录的指针.lmc是Left Most Child的缩写，每个索引分支块都只有一个lmc，这个lmc指向的分支块/叶子块中所有索引键值列中的最大值一定小于该lmc所在过引索分支块的所有索引键值列中的最小值；而索引分支块的索引行记录所记录的指针所指向的分支块/叶子块的所有索引键值列中的最小值一定大于或等于该行记录的索引键值列的值）。
注意：这个键值列不一定是完整的被索引键值，它可能只是被索引键值的前缀。只要Oracle能通过这些前缀区分相应的索引分支块/叶子块就行，这样Oracle就能够既节省索引分支的存储空间，又可以快速定位其下层的索引分支块/叶块。
事实上，如果使用准确的名字来描述关系型数据库中的B-Tree索引，并不能称其为B-Tree索引，而应当称其为B*-Tree索引。
由于没有必要非常准确的学名，所以一般都使用它的广义名称。T-tree索引的结构就像它的名字所表述的意思那样类似一个树结构，从树干开始依次向树枝蔓延，直到树叶。
有人认为是Binary的首字母
有人认为是最早提出该理论的那个人的名字缩写
但更普遍的说法是它是单词“balanced”的首字母缩写---均衡
分支块头部中的“Lmc”是指比分支块中的第一行数据值小的下层数据块的地址（DBA）,使用这种表示方法不仅可以减少块中的所要存储行的数量，而且还能表示“未满”的意思。这里的“未满”是指位于该分支块左边的索引中的值都小于这个分支块中第一行中的值。分枝块中的“Term”代表下层索引块中一部分没有被描述的列值，在这里只是为了简化问题，它有点类似于在比较运算符LIKE中可以把 ‘ABC%’简写为‘ABC’。
看下面的索引结构图：
/+*
drop table gyj_t1;
create table gyj_t1 (
id int,
name varchar2(100)
);
begin
for i in 1 .. 5000 loop
insert into gyj_t1 values(i,‘gyj‘||i);
commit;
end loop;
end;
/
非唯一索引
create index idx_gyj_t1 on gyj_t1(id);
唯一索引
drop index idx_gyj_t1;
create unique index idx_gyj_t1 on gyj_t1(id);
gyj@ZMDB> select object_id from dba_objects where object_name=‘IDX_GYJ_T1‘;
OBJECT_ID
----------
24515
gyj@ZMDB> select header_file,header_block from dba_segments where segment_name=‘IDX_GYJ_T1‘;
HEADER_FILE HEADER_BLOCK
----------- ------------
7 2618
+/
ALTER SESSION SET EVENTS ‘immediate trace name treedump level 24515‘;
----- begin tree dump
branch: 0x1c00a3b 29362747 (0: nrow: 110, level: 1)
--DBA(16进制，10进制)
starting at –1 except root starting at 0
nrow: 110个branck或leaf
level : branch block level (leaf block implicitly 0)
root block split（通常是level发生改变了），branch block split，leaf block split（5-5,9-1）
high=level+1
leaf: 0x1c00a3c 29362748 (-1: nrow: 485 rrow: 485)
除了root其它的都是从-1开始，
nrow: number of all index entries (including deleted entries)
rrow: number of current index entries
level: leaf block implicitly 0
----- end tree dump
*********************************************************************************************转储枝块
alter system dump datafile 7 block 2619;
Branch block dump
=================
header address 139782541810252=0x7f21a8c01a4c
kdxcolev 1 +++index level (0 represents leaf blocks)level为1，
表示这是一个branch block >0 （root block）
KDXCOLEV Flags = - - -
kdxcolok 0 ++++++denotes whether structural block transaction is occurring
表示该索引上是否正在发生修改块结构的事务;
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y +++internal operation code 表示Oracle内部操作代码
kdxconco 2 +++index column count 表示索引条目中列的数量
kdxcosdc 0 +++count of index structural changes involving block
表示索引结构发生变化的数量，当你修改表里的某个索引键值时，该值增加;
kdxconro 109 +++number of index entries (does not include kdxbrlmc pointer)
表示当前索引中的条目数量，不包括lmc指针
kdxcofbo 246=0xf6 +++offset to beginning of free space within block
kdxcofeo 6987=0x1b4b +++offset to the end of free space (i.e.. first portion of block containing index data)
kdxcoavs 6741 +++available space in block (effectively area between kdxcofbo and kdxcofeo)
kdxbrlmc 29362748=0x1c00a3c +++block address if index value is less than the first (row#0) value
kdxbrsno 0 +++last index entry to be modified
表示最后一个被修改的索引第目号，这里看到是0，表示该索引是新建的索引
kdxbrbksz 8056 +++size of usable block space 表示可用数据块的空间大小
kdxbr2urrc 0 +++这里在Oracle内部文档中没有说明，我通过bbed观察没有发现这个结构
row#0[8047] dba: 29362749=0x1c00a3d
col 0; len 3; (3): c2 05 57
col 1; TERM
row#1[8038] dba: 29362750=0x1c00a3e
col 0; len 3; (3): c2 0a 42
col 1; TERM
sys@ZMDB> select UTL_RAW.CAST_TO_NUMBER (‘c20557‘) from dual;
UTL_RAW.CAST_TO_NUMBER(‘C20557‘)
--------------------------------
486 (nrow: 485)
sys@ZMDB> select UTL_RAW.CAST_TO_NUMBER (‘c20a42‘) from dual;
UTL_RAW.CAST_TO_NUMBER(‘C20A42‘)
--------------------------------
965 （nrow: 479 ==> 486+479）
********************************************************************************转储叶块
alter system dump datafile 7 block 2620;
Leaf block dump
===============
header address 140046263134820=0x7f5f0fc42a64
kdxcolev 0 +++index level (0 represents leaf blocks)
KDXCOLEV Flags = - - -
kdxcolok 0 +++denotes whether structural block transaction is occurring(表示结构块事务是否正在发生)
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y +++internal operation code
kdxconco 2 +++index column count
kdxcosdc 0 +++count of index structural changes involving block(包含块的索引结构化改变数目
)
kdxconro 485 +++number of index entries (does not include kdxbrlmc pointer)
kdxcofbo 1006=0x3ee +++offset to beginning of free space within block
kdxcofeo 1830=0x726 +++offset to the end of free space (i.e.. first portion of block containing index data)
kdxcoavs 824 +++available space in block (effectively area between kdxcofbo and kdxcofeo)
kdxlespl 0 +++bytes of uncommitted data at time of block split that have been cleaned out
表示当叶子节点被拆分时未提交的事务数量
kdxlende 0 +++number of deleted entries
表示被删除的索引条目的数量
kdxlenxt 29362749=0x1c00a3d +++pointer to the next leaf block in the index structure via corresponding rba
表示当前叶子节点的下一个叶子节点的地址
kdxleprv 0=0x0 +++pointer to the previous leaf block in the index structure via corresponding
表示当前叶子节点的上一个叶子节点的地址
kdxledsz 0 +++deleted space 表示可用空间，目前是0
kdxlebksz 8032 +++usable block space (by default less than branch due to the additional ITL entry)
row#0[8020] flag: ------, lock: 0, len=12 +++row header(1byte)+flag (2byte) +lock (1byte) + col 8 = 12
+++其中flag表示标记，比如删除标记等，lock表示锁定信息
col 0; len 2; (2): c1 02 +++索引键值
col 1; len 6; (6): 01 c0 00 87 00 00 +++文件号(2byte)+块号(2byte)+行号(2byte)
row#1[8008] flag: ------, lock: 0, len=12
col 0; len 2; (2): c1 03
col 1; len 6; (6): 01 c0 00 87 00 01
gyj@ZMDB> select id,name,dbms_rowid.rowid_relative_fno(rowid) file#,dbms_rowid.rowid_block_number(rowid) block#,dbms_rowid.rowid_row_number(rowid) row# from gyj_t1 where id=1;
ID NAME FILE# BLOCK# ROW#
---------- ---------- ---------- ---------- ----------
1 gyj1 7 135 0
0x01 c0 00 87 00 00===>文件号：01 c0 块号：00 87 行号：00 00
。。。。。。。。。。。。。。。。。。。。。。
理解 B*tree index内部结构