索引的INTERNAL 研究系列之通过TREEDUMP查看二叉树索引的结构

Kevin Zou

2011-8-29

一直觉得对索引的数据存储理解不深，很多时候都是知其然不知其所然，趁现在有时间来研究一下。

觉得要真正研究透索引特性，索引的存储，要看很多的资料，做很多的测试。

现在开始，争取在一个月内完成。

如果要看索引在数据库内的存储总概述，可以通过TREEDUMP 命令来查看。

先找到索引的对象ID,然后通过 ALTER SESSION SET EVENTS 'immediate trace name TREEDUMP level OBJECT_ID' 来DUMP TREEMAP。

SQL> select segment_name, file_id, blocks, block_id 
  2   from dba_extents
  3    where segment_name='I_TEST' and wner='SYS';

SEGMENT_NAME            FILE_ID     BLOCKS   BLOCK_ID
-------------------- ---------- ---------- ----------
I_TEST                        1          8      37641
I_TEST                        1          8      37649
I_TEST                        1          8      37657
I_TEST                        1          8      37665
SQL> select object_id from dba_objects where object_name='I_TEST';

 OBJECT_ID
----------
     65949
SQL> ALTER SESSION SET EVENTS 'immediate trace name TREEDUMP level  65949';
Session altered.

----- begin tree dump
branch: 0x40930a 4231946 (0: nrow: 29, level: 1)
   leaf: 0x40930b 4231947 (-1: nrow: 485 rrow: 485)
   leaf: 0x40930c 4231948 (0: nrow: 479 rrow: 479)
   leaf: 0x40930d 4231949 (1: nrow: 478 rrow: 478)
   leaf: 0x40930e 4231950 (2: nrow: 479 rrow: 479)
   leaf: 0x40930f 4231951 (3: nrow: 479 rrow: 479)
   leaf: 0x409310 4231952 (4: nrow: 479 rrow: 479)
   leaf: 0x409311 4231953 (5: nrow: 479 rrow: 479)
   leaf: 0x409312 4231954 (6: nrow: 478 rrow: 478)
   leaf: 0x409313 4231955 (7: nrow: 479 rrow: 479)
   leaf: 0x409314 4231956 (8: nrow: 479 rrow: 479)
   leaf: 0x409315 4231957 (9: nrow: 479 rrow: 479)
   leaf: 0x409316 4231958 (10: nrow: 479 rrow: 479)
   leaf: 0x409317 4231959 (11: nrow: 479 rrow: 479)
   leaf: 0x409318 4231960 (12: nrow: 479 rrow: 479)
   leaf: 0x409319 4231961 (13: nrow: 479 rrow: 479)
   leaf: 0x40931a 4231962 (14: nrow: 479 rrow: 479)
   leaf: 0x40931b 4231963 (15: nrow: 479 rrow: 479)
   leaf: 0x40931c 4231964 (16: nrow: 479 rrow: 479)
   leaf: 0x40931d 4231965 (17: nrow: 471 rrow: 471)
   leaf: 0x40931e 4231966 (18: nrow: 449 rrow: 449)
   leaf: 0x40931f 4231967 (19: nrow: 449 rrow: 449)
   leaf: 0x409320 4231968 (20: nrow: 449 rrow: 449)
   leaf: 0x409321 4231969 (21: nrow: 449 rrow: 449)
   leaf: 0x409322 4231970 (22: nrow: 449 rrow: 449)
   leaf: 0x409323 4231971 (23: nrow: 448 rrow: 448)
   leaf: 0x409324 4231972 (24: nrow: 448 rrow: 448)
   leaf: 0x409325 4231973 (25: nrow: 449 rrow: 449)
   leaf: 0x409326 4231974 (26: nrow: 449 rrow: 449)
   leaf: 0x409327 4231975 (27: nrow: 404 rrow: 404)
----- end tree dump

DUMP出来的文件描述了索引分布在哪些BLOCK中，每个BLOCK的属于LEAF还是BRANCHE节点，每个block中的内容。

结构说明:

branch/leaf代表该行是分支节点还是页节点（第一行的branch其实是root节点）：

branch: 表示该数据块是branch block （第一行的branch其实是root节点）

leaf: 表示该数据块是leaf block

该节点的rdba，前面是16进制的，后面是10进制的：

0x40930a: 对应索引数据块的十六进位地址；

4231946：对应索引数据块的十进位地址

括号里的第一个数字是同一个level的节点位置计数，root节点从0开始，其他的level从-1开始。

节点中当前的index entry数，从这两个值可以分析出index的空间使用效率；

nrow: 485 ：表示该索引数据块中总的行数，包含被删除的行；

rrow: 485：表示该索引数据块中实际存在有效行数

一般每个索引对象存储块SEGMENT HEADER后第一块，就是ROOT BLOCK。

我这里I_TEST对象的存储的BLOCK是从37641开始分配的空间，连续的32个block。一般索引是SEGMENT HEADER占一个BLOCK（这个未经证实），而第二block=37641+1=37642就是root block.也是我们从TREEDUMP 中看到的第一个branch block的地址。

叶节点有个隐含的level参数，该参数值等于0，也就是说叶节点level 是从0开始的。一直往上直到root 节点。

除了可以看trace文件来看BLEVEL的深度，也可以通过数据字典来查看：

SQL> SELECT blevel FROM dba_indexes WHERE index_name = 'I_TEST';

BLEVEL

----------

1

那整个INDEX的高度计算公式是HEIGHT=BLEVEL+ 1；这个需要通过index_stats 试图来查看，查看前需要先分析下索引结构

SQL> ANALYZE INDEX I_TEST VALIDATE STRUCTURE;

Index analyzed.

SQL> select height from index_stats where name ='I_TEST';

HEIGHT

----------

2

得到BLOCK的地址后，可以通过dbms_utility package 来查询对应的FILE和BLOCK：

SQL> select dbms_utility.data_block_address_file(4231946) "file",dbms_utility.data_block_address_block(4231946) "block" from dual;

file block

---------- ----------

1 37642

-THE END-

ITPub博客

索引的INTERNAL 研究系列之通过TREEDUMP查看二叉树索引的结构

最新文章

ITPub博客

索引的INTERNAL 研究系列 之通过TREEDUMP查看二叉树索引的结构

最新文章

索引的INTERNAL 研究系列之通过TREEDUMP查看二叉树索引的结构