分享程序员开发的那些事...
更新时间：2022-09-06 23:36:36
[20160711]索引键值在B tree索引块中的顺序.txt
--昨天听课,又有人在这个问题上错误.实际上索引键值是"块中无序,块间有序",以前看的连接:
--参考链接：http://www.adellera.it/blog/2009/05/24/order-keys-inside-index-blocks/
--http://blog.itpub.net/267265/viewspace-713847/
--当时不熟悉bbed,今天通过bbed观察来讲解:
1.环境:
SCOTT@test01p> @ ver1
PORT_STRING VERSION BANNER CON_ID
------------------------------ -------------- -------------------------------------------------------------------------------- ----------
IBMPC/WIN_NT64-9.1.0 12.1.0.1.0 Oracle Database 12c Enterprise Edition Release 12.1.0.1.0 - 64bit Production 0
create table t (x varchar2(10));
insert into t values('000000');
insert into t values('777777');
insert into t values('111111');
insert into t values('666666');
insert into t values('222222');
insert into t values('555555');
insert into t values('333333');
insert into t values('444444');
commit ;
create index i_t_x on t(x);
2.观察:
SCOTT@test01p> select header_file,header_block from dba_segments where owner='SCOTT' and segment_name='I_T_X';
HEADER_FILE HEADER_BLOCK
----------- ------------
9 178
--//dba=9,179 就是索引的root节点.
SYS@test> alter system dump datafile 9 block 179;
System altered.
--检查转储文件:
018094140 00000000 00000000 37060000 37373737 [...........77777]
018094150 40020637 01008D00 36060000 36363636 [7..@.......66666]
018094160 40020636 03008D00 35060000 35353535 [6..@.......55555]
018094170 40020635 05008D00 34060000 34343434 [5..@.......44444]
018094180 40020634 07008D00 33060000 33333333 [4..@.......33333]
018094190 40020633 06008D00 32060000 32323232 [3..@.......22222]
0180941A0 40020632 04008D00 31060000 31313131 [2..@.......11111]
0180941B0 40020631 02008D00 30060000 30303030 [1..@.......00000]
0180941C0 40020630 00008D00 00000000 00000000 [0..@............]
0180941D0 00000000 00000000 00000000 00000000 [................]
Repeat 1 times
0180941F0 00000000 00000000 00000000 04FE0601 [................]
--//从块内容看,里面的键值是排序的(数据从块底部开始插入的),实际上我插入数据在前,建立索引在后,这样索引里面的检查是排序的.
3.如果先建立索引,再插入数据呢?
SCOTT@test01p> truncate table t ;
Table truncated.
insert into t values('000000');
insert into t values('777777');
insert into t values('111111');
insert into t values('666666');
insert into t values('222222');
insert into t values('555555');
insert into t values('333333');
--insert into t values('444444');
commit ;
--//注解其中一行.
SCOTT@test01p> select header_file,header_block from dba_segments where owner='SCOTT' and segment_name='I_T_X';
HEADER_FILE HEADER_BLOCK
----------- ------------
9 178
--//dba=9,179 就是索引的root节点.
SYS@test> alter system dump datafile 9 block 179;
System altered.
018094150 00000000 00000000 33060200 33333333 [...........33333]
018094160 40020633 06008D00 35060200 35353535 [3..@.......55555]
018094170 40020635 05008D00 32060200 32323232 [5..@.......22222]
018094180 40020632 04008D00 36060200 36363636 [2..@.......66666]
018094190 40020636 03008D00 31060200 31313131 [6..@.......11111]
0180941A0 40020631 02008D00 37060200 37373737 [1..@.......77777]
0180941B0 40020637 01008D00 30060200 30303030 [7..@.......00000]
0180941C0 40020630 00008D00 00000000 00000000 [0..@............]
0180941D0 00000000 00000000 00000000 00000000 [................]
Repeat 1 times
0180941F0 00000000 00000000 00000000 0A0F0601 [................]
--可以发现索引键值按照插入顺序排列的.也就是在块中是无序的.
BBED> set dba 9,180
DBA 0x024000b4 (37748916 9,180)
--//我使用windows 的bbed ,存在1个数据块偏移(由于无法识别数据文件头)
BBED> p kd_off
b2 kd_off[0] @132 8036
b2 kd_off[1] @134 0
b2 kd_off[2] @136 8020
b2 kd_off[3] @138 7988
b2 kd_off[4] @140 7956
b2 kd_off[5] @142 7924
b2 kd_off[6] @144 7940
--使用bbed看索引kd_off结构,存在问题前面4个字节不是.
BBED> dump offset 146 count 2
File: D:\APP\ORACLE\ORADATA\TEST\TEST01P\SAMPLE_SCHEMA_USERS01.DBF (9)
Block: 180 Offsets: 146 to 147 Dba:0x024000b4
-----------------------------------------------------------------------
241f
<64 bytes per line>
--0x1f24 = 7972
BBED> dump offset 148 count 2
File: D:\APP\ORACLE\ORADATA\TEST\TEST01P\SAMPLE_SCHEMA_USERS01.DBF (9)
Block: 180 Offsets: 148 to 149 Dba:0x024000b4
----------------------------------------------------------------------
441f
<64 bytes per line>
-- 0x1f44 = 8004
--最小是b2 kd_off[5] @142 7924
4.如果看行目录kd_off:
--可以发现是排序的按照kd_off指向的偏移检索。
BBED> p *kd_off[2]
rowdata[100]
------------
ub1 rowdata[100] @8120 0x00
BBED> x /rcx
rowdata[100] @8120
------------
flag@8120: 0x00 (NONE)
lock@8121: 0x02
data key:
col 0[6] @8123: 000000
col 1[6] @8130: 0x02 0x40 0x00 0x8d 0x00 0x00
BBED> p *kd_off[3]
rowdata[68]
-----------
ub1 rowdata[68] @8088 0x00
BBED> x /rcx
rowdata[68] @8088
-----------
flag@8088: 0x00 (NONE)
lock@8089: 0x02
data key:
col 0[6] @8091: 111111
col 1[6] @8098: 0x02 0x40 0x00 0x8d 0x00 0x02
BBED> p *kd_off[4]
rowdata[36]
-----------
ub1 rowdata[36] @8056 0x00
BBED> x /rcx
rowdata[36] @8056
-----------
flag@8056: 0x00 (NONE)
lock@8057: 0x02
data key:
col 0[6] @8059: 222222
col 1[6] @8066: 0x02 0x40 0x00 0x8d 0x00 0x04
...
--//看最后1个偏移,注意要加100+8004=8104.
BBED> x /rcx offset 8104
rowdata[84] @8104
-----------
flag@8104: 0x00 (NONE)
lock@8105: 0x02
data key:
col 0[6] @8107: 777777
col 1[6] @8114: 0x02 0x40 0x00 0x8d 0x00 0x01
5.再插入看看:
insert into t values('444444');
commit ;
alter system checkpoint ;
--再通过bbed观察kd_off:
BBED> set dba 9,180
DBA 0x024000b4 (37748916 9,180)
BBED> p kd_off
b2 kd_off[0] @132 8036
b2 kd_off[1] @134 0
b2 kd_off[2] @136 8020
b2 kd_off[3] @138 7988
b2 kd_off[4] @140 7956
b2 kd_off[5] @142 7924
b2 kd_off[6] @144 7908
b2 kd_off[7] @146 7940
--//如果你对比前面的行目录,可以发现插入kd_off[6]=7908,对应的索引键值就是'44444'.后面的kd_off[7]=原来的kd_off[6]=7940,
--//后面的行目录依次后移。
BBED> x /rcx *kd_off[6]
rowdata[4] @8008
----------
flag@8008: 0x00 (NONE)
lock@8009: 0x02
data key:
col 0[6] @8011: 444444
col 1[6] @8018: 0x02 0x40 0x00 0x8d 0x00 0x07
--也就是当插入数据修改索引键值,只要通过索引行目录kd_off通过二分法确定位置,也就是要维持索引键值顺序,仅仅维护行目录指向的
--键值是排序的.
--总之:
1.正常索引的键值就是块内无序,块间有序.
2.也就是排序仅仅按照行目录指向的键值排序，以后检索或者插入键值应该通过2分发定位，减少检索的对比次数。