理解 B*tree index内部结构

标签: 理解 tree index | 发表时间:2014-10-30 02:05 | 作者:guoyJoe
出处:http://blog.csdn.net


转载请注明出处: 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);


[email protected]> select object_id from dba_objects where object_name='IDX_GYJ_T1';

 OBJECT_ID
----------
     24515

[email protected]> 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


[email protected]> select UTL_RAW.CAST_TO_NUMBER ('c20557') from dual;

UTL_RAW.CAST_TO_NUMBER('C20557')
--------------------------------
                             486    (nrow: 485)


[email protected]> 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


[email protected]> 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


。。。。。。。。。。。。。。。。。。。。。。

 

作者:guoyJoe 发表于2014-10-29 18:05:39 原文链接
阅读:184 评论:0 查看评论

相关 [理解 tree index] 推荐:

理解 B*tree index内部结构

- - CSDN博客数据库推荐文章
转载请注明出处: http://write.blog.csdn.net/postedit/40589651.     Oracle数据库里的B树索引就好象一棵倒长的树,它包含两种类型的数据块:一种是索引分支块,另一种是索引叶子块 索引分支块包含指向相应索引分支块/叶子块的指针和索引健值列(这里的指针是指相关分支块/叶子块的块地址RDBA.

XML to tree XML 树

- Bloger - 博客园-首页原创精华区
前面发了一个 html to tree 再发一个 xml to tree. 版权所有:版权所有(C) 2009. 文件名称:xml2tree.js. 完成日期:2009-12-22. 页:http://www.chaige.net */ var XML2Tree = function (ini) {.

CSS中的z-index属性

- - IT技术博客大学习
标签:   z-index. css中z-index也是常用的一个属性,这个z-index说的就是第三轴的位置,网页实际是二维的,但是页面上的元素堆叠的层次就可以看作为第三轴,所以z-index也就很好理解了,在z轴上的索引. 好吧我再说的直白一点这里的z-index指的就是哪个元素显示在上面,哪个显示在下面,数值越大的越靠上,会把z-index值比较小的元素挡住.

露天小便器P-tree

- Haitao - 设计|生活|发现新鲜
2011年丹麦洛斯基尔德音乐节吸引超过10万的游客,强大的人流量对城市的公共厕所的需求也提出了考验. 但丹麦的AANDEBOOM公司却巧妙的解决了这一问题. 他们设计了50个露天小便器,分别放在主会场附近的2个不同街道. 事实证明,它确实是成功的,有大量游客乐意使用它. 这小便器还有个可爱的名字,P-Tree,向大树尿尿,顿时想到小公狗,翘起腿朝树上尿尿哦.

emacs 新手必看: undo-tree

- leafduo - LinuxTOY
火星人都知道,emacs 只有 undo ,没有 redo ……或者说它有 redo,但是相当的诡异,套用一句经典台词就是: 猥琐,非常的猥琐. 简单的说,emacs 的 redo 就是 undo undo ,也就是传说中的负负得正. 可能有些 emacs 新手,还不知道怎么去操作,因为一般情况下,无论你 undo 多少次,都不会发生 redo 的现象.

[转][转]TokuDB中的COLA-Tree和TokuMax中的Fractal tree(分形树)

- - heiyeluren的blog(黑夜路人的开源世界)
TokuDB中的COLA-Tree.       目前无论是商业的SQL Server,还是开源的MySQL,都基本上还在用比较老的 B+Tree(SQL Server用的是标准的B-Tree)的索引结构. 从原理来说,B系列树在查询过程中应该是不会慢的,而主要问题就是出现在插入. B-Tree在插入的时候,如果是最后一个node,那么速度非常快,因为是顺序写.

关于z-index的那些事儿

- - 前端观察
关于z-index的真正问题是,很少有人理解它到底是怎么用. 其实它并不复杂,但是如果你从来没有花一定时间去看具体的z-index相关文档,那么你很可能会忽略一些重要的信息. 好吧,看看你能否解决下面这个问题:. 在 接下来的HTML里 有三个
元素,并且每个
里包含一个元素.

index rebuild和rebuild online的区别

- - CSDN博客数据库推荐文章
       曾经看到过淘宝的这个面试题:在一个24*7的应用上,需要把一个访问量很大的1000万以上数据级别的表的普通索引(a,b)修改成唯一约束(a,b,c),你一般会选择怎么做,请说出具体的操作步骤与语句.        先online建索引添加约束,然后删除原理的索引.        为什么要用online呢.

zTree v2.6.03 发布,JQuery Tree插件

- pathfinder - ITeye资讯频道
JQuery Tree插件zTree v2.6.03 发布了. zTree 是利用 JQuery 的核心代码,实现一套能完成大部分常用功能的 Tree 插件. 该版本修正了一些重要的bug:. 【修正】使用自定义图标功能时,异步加载无法切换为loading图标的bug. 【修正】loading 图标定义中的1像素差异,否则会导致高级异步加载中loading跳动(更新 zTreeStyle.css 和 bigDataDemo_super.html).

js Tree - 树形菜单插件

- We_Get - 博客园-首页原创精华区
      js Tree - 树形菜单.       1)DTree是 JQuery 著名树形插件Dynatree的包装类,增加右键菜单,添加、删除、更新接口.     2)jquery treeList widget 这是一个利用jQuery UI Widget Factory创建的轻量级,可换肤树形列表控件.