ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 数据库 > Oracle > b*tree index的那些事(二):索引结构分析

b*tree index的那些事(二):索引结构分析

Oracle 作者：dreamllover 时间：2016-05-30 15:55:26 0 删除 编辑

B*tree index结构分析


  1. SQL> drop table lxy purge;

  3. Table dropped.

  5. SQL> create table lxy (a char(2000));

  7. Table created.

  9. SQL> create index idx_lxy_a on lxy(a);

  11. Index created.

  13. SQL> insert into lxy select rownum from dual connect by rownum<=1000;

  15. 1000 rows created.

  17. SQL> /

  19. 1000 rows created.

  21. SQL> commit;

  23. Commit complete.

  25. SQL> select object_id from dba_objects where object_name='IDX_LXY_A';

  27.  OBJECT_ID
  28. ----------
  29.      14328

  31. SQL> alter session set events 'immediate trace name treedump level 14328'; 

  33. Session altered.

treedump：
  1. ----- begin tree dump
  2. branch: 0x4087b9 4229049 (0: nrow: 3, level: 2)            --root block(dba=4229049;level=2 索引层级号;nrow=3 有3个branch block)
  3.    branch: 0x408d67 4230503 (-1: nrow: 379, level: 1)      --branch block(dba=4230503;level=1;nrow=379 该branch block有379个leaf block)
  4.       leaf: 0x4087ba 4229050 (-1: nrow: 2 rrow: 2)         --leaf block(nrow=2 该leaf block下有2个index entries;rrow=2 有2个non-deleted entris)
  5.       leaf: 0x408af3 4229875 (0: nrow: 2 rrow: 2)
  6.       leaf: 0x408aea 4229866 (1: nrow: 2 rrow: 2)
  7.       leaf: 0x408eec 4230892 (2: nrow: 2 rrow: 2)
  8.       ...
  9.       leaf: 0x4089a0 4229536 (376: nrow: 2 rrow: 2)
  10.       leaf: 0x408d13 4230419 (377: nrow: 2 rrow: 2)
  11.    branch: 0x408d68 4230504 (0: nrow: 620, level: 1)       --branch block
  12.       leaf: 0x408999 4229529 (-1: nrow: 2 rrow: 2)
  13.       leaf: 0x408d14 4230420 (0: nrow: 2 rrow: 2)
  14.       leaf: 0x408b92 4230034 (1: nrow: 2 rrow: 2)
  15.       ...
  16.       leaf: 0x408ee8 4230888 (617: nrow: 2 rrow: 2)
  17.       leaf: 0x408ae9 4229865 (618: nrow: 3 rrow: 3)
  18.    branch: 0x408eeb 4230891 (1: nrow: 1, level: 1)         --branch block
  19.       leaf: 0x408eea 4230890 (-1: nrow: 1 rrow: 1)
  20. ----- end tree dump


root block

  • 1.Every index has one root block
  • 2.May be a leaf block or a branch block
  • 3.Can be an empty leaf block
  • 4.Always the next block after the segment header in the first extent

  1. select header_block,
  2.        header_file,
  3.      DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(4229049) root_fno,
  4.      DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(4229049) root_bno 
  5.   from dba_segments 
  6.  where segment_name='IDX_LXY_A';

HEADER_BLOCK HEADER_FILE   ROOT_FNO   ROOT_BNO
------------ ----------- ---------- ----------
       34744           1          1      34745      --ROOT_BNO=HEADER_BLOCK+1
root block dump：

  1. -- dump root block：branch: 0x4087b9 4229049 (0: nrow: 3, level: 2)
  2. SQL> alter system dump datafile 1 block 34745;


  5. System altered.


  1. Branch block dump
  2. =================
  3. header address 140112751121988=0x7f6e8ac25644
  4. kdxcolev 2 --索引层级(叶子块的层级为0),该索引高度为3,所以这个块是root block,branch block的kdxcolev=1
  5. KDXCOLEV Flags = - - -
  6. kdxcolok 1 --Itl的条目数
  7. kdxcoopc 0x81: opcode=1: iot flags=--- is converted=Y
  8. kdxconco 2 --索引条目中列的数量
  9. kdxcosdc 2 --该索引块结构发生变化的次数
  10. kdxconro 2 --root block的索引条目数,但是不包括kdxbrlmc pointer
  11. kdxcofbo 32=0x20 --空闲空间的偏移量起点
  12. kdxcofeo 6038=0x1796 --空闲空间的偏移量终点
  13. kdxcoavs 6006 --可用空间量=kdxcofeo-kdxcofbo
  14. kdxbrlmc 4230503=0x408d67 --如果索引键值小于row#0的col 0,就指向在kdxbrlmc对应的branch block上,这里即dba=4230503
  15. kdxbrsno 1 --最后更改的索引条目,这里即row#1[6038] dba: 4230891=0x408eeb
  16. kdxbrbksz 8056 --该块可用空间大小
  17. kdxbr2urrc 0
  18. row#0[8048] dba: 4230504=0x408d68 --branch block的dba
  19. col 0; len 2; (2): 34 34          --该branch block对应的kdxbrlmc所指向的leaf block的第一条索引条目的索引键值或索引键值前缀
  20. col 1; TERM                       --当col 0为索引键值前缀时,col 1为TERM
  21. row#1[6038] dba: 4230891=0x408eeb --branch block的dba
  22. col 0; len 2000; (2000): 39 39 39 20...20 --该branch block对应的kdxbrlmc所指向的leaf block的第一条索引条目的索引键值或索引键值前缀
  23. col 1; len 3; (3): 00 40 8f --当col 0为完整索引键值时,col 1为该索引键值对应的rowid或rowid前缀

root block的总结(index的height=3)：
1.该root block分别有3个branch block,顺序为kdxbrlmc,row#0,row#1
2.每个root block都只有一个lmc,这个lmc指向的branch block的最后一个leaf block的最后一条索引条目的索引键值一定小于等于row#0指向的branch block的第一个leaf block的第一条索引条目的索引键值,row#0与row#1同上
3.root block的行记录所对应的存储格式为:行头 + branch block的DBA + col 0 + col 1,其中col 0为该行行头branch block对应的kdxbrlmc所指向的leaf block的第一条索引条目的索引键值或索引键值前缀
  •    1)当行头对应的branch block的对应的kdxbrlmc所指向的leaf block的第一条索引条目的索引键值>上一个branch block对应的最后一个leaf block的最后一条索引条目的索引键值时,此时col 0为该行行头branch block对应的kdxbrlmc所指向的leaf block的第一条索引条目的索引键值前缀,因为不需要再用rowid来保证索引逻辑的顺序,所以此时col 1为固定值TERM
  •    2)当行头对应的branch block的对应的kdxbrlmc所指向的leaf block的第一条索引条目的索引键值=上一个branch block对应的最后一个leaf block的最后一条索引条目的索引键值时,此时col 0为该行行头branch block对应的kdxbrlmc所指向的leaf block的第一条索引条目的完整索引键值,且需要用rowid来保证索引逻辑的顺序,此时col 1为对应ROWID或ROWID前缀

对于该root block的例子(索引字段类型为char(2000)):
row#0[8048] dba: 4230504=0x408d68
col 0; len 2; (2):  34 34 --明显是索引键值前缀,转化为实际值则是'44'后面补位的null省略,所以该root block的lmc指向的branch block的最后一个leaf block的最后一条索引条目的索引键值一定<'44'
col 1; TERM               --这里无需使用ROWID来保证索引逻辑的顺序,所以为TERM
row#1[6038] dba: 4230891=0x408eeb
col 0; len 2000; (2000): 39 39 39 20...20 --完整索引键值,转化为实际值则是rtrim(col 0)='999',上一个branch block即row#0对应的branch block的最后一个leaf block的最后一条索引条目的索引键值一定等于'999'
col 1; len 3; (3):  00 40 8f  --且上一个branch block的最后一个leaf block的最后一条索引条目的索引键值的ROWID一定前两位是'00 40'后1位小于'8f'

验证:
该root block的lmc指向的branch block(dba=4230503)的最后一个leaf block(通过dump块4230503得到dba=4230419)的最后一条索引条目的索引键值为：
row#1[6021] flag: ------, lock: 2, len=2011
col 0; len 2000; (2000): 34 33 39 20...20  --转化为实际值为'439'后面补位的null省略,'439'<'44'
col 1; len 6; (6):  00 40 8c 60 00 01
row#0对应的branch block(dba=4230504)的最后一个leaf block(dba=4229865)的最后一条索引条目的索引键值为:
row#2[6021] flag: ----S-, lock: 2, len=2011
col 0; len 2000; (2000): 39 39 39 20...20 --转化为实际值为'999'后面补位的null省略,'999'='999'
col 1; len 6; (6):  00 40 8b 4d 00 02 --和之前结论也一致

说明之前的总结得出的结论都是正确的
     

  • kdxcolev: index level (0 represents leaf blocks) 
  • kdxcolok: denotes whether structural block transaction is occurring 
  • kdxcoopc: internal operation code 
  • kdxconco: index column count 
  • kdxcosdc: count of index structural changes involving block 
  • kdxconro: number of index entries (does not include kdxbrlmc pointer) 
  • kdxcofbo: offset to beginning of free space within block 
  • kdxcofeo: offset to the end of free space (i.e.. first portion of block containing index data) 
  • kdxcoavs: available space in block (effectively area between kdxcofbo and kdxcofeo)
  • kdxbrlmc: block address if index value is less than the first (row#0) value （每个root block或branch block都有且只有1个kdxbrlmc)
  • kdxbrsno: last index entry to be modified 
  • kdxbrbksz: size of usable block space

branch block

  • 1.Indexes may contain branch blocks
  • 2.Branch blocks point to other branch blocks or leaf blocks
  • 3.Branch blocks contain 0 or more rows
  • 4.Each row has a suffix compressed key and a pointer to the next block
  • 5.Compressed rows are terminated with 0xFE byte
  • 6.Each block has a pointer to the left hand side of the tree. This is part of the header
  • 7.A branch block containing N rows points to N+1 blocks.
root block下共有3个branch block：
branch: 0x408d67 4230503 (-1: nrow: 379, level: 1)
branch: 0x408d68 4230504 (0: nrow: 620, level: 1)
branch: 0x408eeb 4230891 (1: nrow: 1, level: 1)

随便dump一个branch block：

  1. SQL> select DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(4230504) fno,DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(4230504) bno from dual;

  3.        FNO BNO
  4. ---------- ----------
  5.          1 36200

  7. SQL> ALTER SYSTEM DUMP DATAFILE 1 BLOCK 36200;

  9. System altered.
branch block的结构和root block几乎一致

  1. Branch block dump
  2. =================
  3. header address 140186507995716=0x7f7fb702ea44
  4. kdxcolev 1
  5. KDXCOLEV Flags = - - -
  6. kdxcolok 1
  7. kdxcoopc 0x85: opcode=5: iot flags=--- is converted=Y
  8. kdxconco 2
  9. kdxcosdc 1
  10. kdxconro 619
  11. kdxcofbo 1266=0x4f2
  12. kdxcofeo 2550=0x9f6
  13. kdxcoavs 1284
  14. kdxbrlmc 4229529=0x408999
  15. kdxbrsno 616
  16. kdxbrbksz 8056
  17. kdxbr2urrc 0
  18. row#0[4863] dba: 4230420=0x408d14 --leaf block的dba
  19. col 0; len 3; (3): 34 34 30       --该leaf block的第一条索引条目的索引键值或前缀
  20. col 1; TERM                       --当col 0为索引键值前缀时,col 1为TERM;当col 0为完整索引键值时col 1为该leaf block的第一条索引条目的ROWID或前缀
  21. row#1[4872] dba: 4230034=0x408b92
  22. col 0; len 3; (3): 34 34 31
  23. col 1; TERM
  24. row#2[4881] dba: 4229537=0x4089a1
  25. col 0; len 3; (3): 34 34 32
  26. col 1; TERM
  27. row#3[4890] dba: 4230422=0x408d16
  28. col 0; len 3; (3): 34 34 33
  29. col 1; TERM
  30. ...
  31. row#617[2559] dba: 4230888=0x408ee8
  32. col 0; len 3; (3): 39 39 37
  33. col 1; TERM
  34. row#618[8047] dba: 4229865=0x408ae9
  35. col 0; len 3; (3): 39 39 38
  36. col 1; TERM

branch block的总结(index的height=3)：
1.该branch block分别有620个branch block
2.每个branch block都只有一个lmc,这个lmc指向的leaf block的最后一条索引条目的索引键值一定小于等于row#0指向的leaf block的第一条索引条目的索引键值
3.branch block的行记录所对应的存储格式为:行头 + leaf block的DBA + col 0 + col 1,其中col 0为该行行头leaf block对应的的第一条索引条目的索引键值或索引键值前缀
  •    1)当行头对应的leaf block的对应的leaf block的第一条索引条目的索引键值>该leaf block对应kdxleprv所指向的leaf block的最后一条索引条目的索引键值时,此时col 0为该行行头leaf block的第一条索引条目的索引键值前缀,因为不需要再用rowid来保证索引逻辑的顺序,所以此时col 1为固定值TERM
  •    2)当行头对应的leaf block的对应的leaf block的第一条索引条目的索引键值=该leaf block对应kdxleprv所指向的leaf block的最后一条索引条目的索引键值时,此时col 0为该行行头leaf block的第一条索引条目的完整索引键值,且需要用rowid来保证索引逻辑的顺序,此时col 1为对应ROWID或ROWID前缀,只要能和kdxleprv所指向的叶子块的最后一行索引行所对应的数据行的ROWID区分开就行，可以不是完整的ROWID

NOTE:Internal ROWID are used in branch blocks Always 4 bytes.

leaf block

  • 1.Every index has a least one leaf block
  • 2.Each leaf block contains 0 or more rows
  • 3.Each row contains a key and data
  • 4.Indexes can be unique or non-unique
  • 5.Leaf row formats differ for unique and non-unique indexes

  1. SQL> select DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE(4230422) fno,DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK(4230422) bno from dual;

  3.        FNO BNO
  4. ---------- ----------
  5.          1 36118

  1. --row#3[4890] dba: 4230422=0x408d16
  2. Leaf block dump
  3. ===============
  4. header address 140186507995740=0x7f7fb702ea5c
  5. kdxcolev 0
  6. KDXCOLEV Flags = - - -
  7. kdxcolok 1
  8. kdxcoopc 0x87: opcode=7: iot flags=--- is converted=Y
  9. kdxconco 2
  10. kdxcosdc 1
  11. kdxconro 2
  12. kdxcofbo 40=0x28
  13. kdxcofeo 4010=0xfaa
  14. kdxcoavs 3970
  15. kdxlespl 0
  16. kdxlende 0
  17. kdxlenxt 4230421=0x408d15
  18. kdxleprv 4229537=0x4089a1
  19. kdxledsz 0
  20. kdxlebksz 8032
  21. row#0[4010] flag: ----S-, lock: 2, len=2011
  22. col 0; len 2000; (2000): 34 34 33 20 ... 20
  23. col 1; len 6; (6): 00 40 8a 14 00 01
  24. row#1[6021] flag: ------, lock: 2, len=2011
  25. col 0; len 2000; (2000): 34 34 33 20 ... 20
  26. col 1; len 6; (6): 00 40 8c 61 00 02
  • 1.kdxlespl: bytes of uncommitted data at time of block split that have been cleaned out 
  • 2.kdxlende: number of deleted entries 
  • 3.kdxlenxt: pointer to the next leaf block in the index structure via corresponding rba 
  • 4.kdxleprv: pointer to the previous leaf block in the index structure via corresponding rba 
  • 5.Kdxledsz: deleted space 
  • 6.kdxlebksz: usable block space (by default less than branch due to the additional ITL entry)
NOTE:External ROWIDs are used in leaf blocks

Bytes

Description

6

Local Indexes

8

Cluster Indexes

10

Global Indexes

32

LOB Indexes



来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/30875621/viewspace-2109315/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： b*tree index的那些事(一):索引简介
下一篇： 没有了~
请登录后发表评论 登录
全部评论
dreamllover

注册时间：2016-02-16

  • 博文量
    3
  • 访问量
    9019

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593