[php]
B-Tree Index的结构浅探
1 准备测试环境 ads3+10g 10.1.0.2
SQL> create table t1(id number,name varchar2(32));
Table created.
SQL> insert into t1 select rownum,object_name as name from dba_objects;
10666 rows created.
SQL> create index idx_t1_id on t1(id);
Index created.
SQL> create index idx_t1_name on t1(name);
Index created.
SQL> create index idx_t1_id_name on t1(id,name);
Index created.
2 数值字段上的索引
SQL> analyze index idx_t1_id validate structure;
Index analyzed.
Elapsed: 00:00:00.04
SQL> exec print_table('select * from index_stats');
HEIGHT
: 2
BLOCKS
: 32
NAME
: IDX_T1_ID
PARTITION_NAME
:
LF_ROWS
: 10666
LF_BLKS
: 23
LF_ROWS_LEN
: 160451
LF_BLK_LEN
: 7996
BR_ROWS
: 22
BR_BLKS
: 1
BR_ROWS_LEN
: 244
BR_BLK_LEN
: 8028
DEL_LF_ROWS
: 0
DEL_LF_ROWS_LEN
: 0
DISTINCT_KEYS
: 10666
MOST_REPEATED_KEY
: 1
BTREE_SPACE
: 191936
USED_SPACE
: 160695
PCT_USED
: 84
ROWS_PER_KEY
: 1
BLKS_GETS_PER_ACCESS
: 3
PRE_ROWS
: 0
PRE_ROWS_LEN
: 0
OPT_CMPR_COUNT
: 0
OPT_CMPR_PCTSAVE
: 0
-----------------
SQL> select file_id,extent_id,block_id,blocks
from dba_extents where segment_name='IDX_T1_ID';
FILE_IDEXTENT_ID BLOCK_ID BLOCKS
---------- ---------- ---------- ----------
5
0417
8
5
1425
8
5
2433
8
5
3441
8
SQL> alter system dump datafile 5 block min 417 block max 424;
System altered.
SQL> select data_object_id from dba_objects where object_name ='IDX_T1_ID';
DATA_OBJECT_ID
--------------
12905
SQL> select file#,block# from sys.ind$ where dataobj#=12905;
FILE# BLOCK#
---------- ----------
5419
通过dump的文件可知
block# 417 block: FIRST LEVEL BITMAP BLOCK
block# 418 block: SECOND LEVEL BITMAP BLOCK
block# 419 block: PAGETABLE SEGMENT HEADER
现在可以看看一第个branch block的内容......
buffer tsn: 7 rdba: 0x014001a4 (5/420)
scn: 0x0000.003c04dd seq: 0x01 flg: 0x04 tail: 0x04dd0601
frmt: 0x02 chkval: 0xe5d9 type: 0x06=trans data
Block header dump:0x014001a4
Object id on Block? Y
seg/obj: 0x3269csc: 0x00.3c04d2itc: 1flg: Etyp: 2 - INDEX
brn: 0bdba: 0x14001a1 ver: 0x01 opc: 0
inc: 0exflg: 0
Itl Xid
Uba FlagLckScn/Fsc
0x01 0xffff.000.000000000x00000000.0000.00C---0scn 0x0000.003c04d2
Branch block dump
=================
header address 196782668=0xbbaaa4c
kdxcolev 1
KDXCOLEV Flags = - - -
kdxcolok 0
kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y
kdxconco 2
kdxcosdc 0
kdxconro 22
kdxcofbo 72=0x48
kdxcofeo 7856=0x1eb0
kdxcoavs 7784
kdxbrlmc 20971941=0x14001a5这个是第一个leaf block,除了kdxbrlmc记录的leaf block外
kdxbrsno 0
下面列表中共列了22个leaf block(row#0-row#21),如果id=8
kdxbrbksz 8056
的查询,oracle判断小于486,就会去遍历第1个leaf block kdxbr2urrc 0
0x14001a5块。
row#0[8047] dba: 20971942=0x14001a6 这个是第二个leaf block
col 0; len 3; (3):c2 05 57=> 486(后面附有逆向运算的函数)
col 1; TERM
row#1[8038] dba: 20971943=0x14001a7
col 0; len 3; (3):c2 0a 42=> 965
col 1; TERM
row#2[8029] dba: 20971944=0x14001a8
col 0; len 3; (3):c2 0f 2d
col 1; TERM
row#3[8020] dba: 20971945=0x14001a9
col 0; len 3; (3):c2 14 18
col 1; TERM
row#4[8011] dba: 20971946=0x14001aa
col 0; len 3; (3):c2 19 03
col 1; TERM
row#5[8002] dba: 20971947=0x14001ab
col 0; len 3; (3):c2 1d 51
col 1; TERM
row#6[7993] dba: 20971948=0x14001ac
col 0; len 3; (3):c2 22 3c
col 1; TERM
row#7[7984] dba: 20971949=0x14001ad
col 0; len 3; (3):c2 27 27
col 1; TERM
row#8[7975] dba: 20971950=0x14001ae
col 0; len 3; (3):c2 2c 12
col 1; TERM
row#9[7966] dba: 20971951=0x14001af
col 0; len 3; (3):c2 30 60
col 1; TERM
row#10[7957] dba: 20971952=0x14001b0
col 0; len 3; (3):c2 35 4b
col 1; TERM
row#11[7948] dba: 20971954=0x14001b2
col 0; len 3; (3):c2 3a 36
col 1; TERM
row#12[7939] dba: 20971955=0x14001b3
col 0; len 3; (3):c2 3f 21
col 1; TERM
row#13[7930] dba: 20971956=0x14001b4
col 0; len 3; (3):c2 44 0c
col 1; TERM
row#14[7921] dba: 20971957=0x14001b5
col 0; len 3; (3):c2 48 5a
col 1; TERM
row#15[7912] dba: 20971958=0x14001b6
col 0; len 3; (3):c2 4d 45
col 1; TERM
row#16[7903] dba: 20971959=0x14001b7
col 0; len 3; (3):c2 52 30
col 1; TERM
row#17[7894] dba: 20971960=0x14001b8
col 0; len 3; (3):c2 57 1b
col 1; TERM
row#18[7885] dba: 20971961=0x14001b9
col 0; len 3; (3):c2 5c 06
col 1; TERM
row#19[7876] dba: 20971962=0x14001ba
col 0; len 3; (3):c2 60 54
col 1; TERM
row#20[7866] dba: 20971963=0x14001bb
col 0; len 4; (4):c3 02 01 3b
col 1; TERM
row#21[7856] dba: 20971964=0x14001bc
col 0; len 4; (4):c3 02 06 08
col 1; TERM
----- end of branch block dump -----
oracle数据存储方式
http://www.itpub.net/211094.html
关于求branch block中索引项最小值的函数：
create or replace function uf_dec(v_hex in varchar2)
return number
as
v_num varchar2(99);
v_lef varchar2(99);
v_str char(2);
v_dec number;
v_len number;
v_ins number;
begin
v_lef := v_hex;
v_str := trim(substr(v_lef,1,3));
v_len := length(v_str);
while v_len > 0 loop
select to_number(v_str,'xx') into v_dec from dual;
if v_num is null then
v_num := v_num || v_dec;
else
v_num := v_num ||','||v_dec;
end if;
v_lef := substr(v_lef,4);
v_str := trim(substr(v_lef,1,3));
v_len := length(v_str);
end loop;
for i in 0 .. 1000000 loop
select instr(dump(i),v_num) into v_ins from dual;
if v_ins > 0 then
return i;
exit;
end if;
end loop;
end;
示例：
SQL> select uf_dec('&input_hex') from dual;
Enter value for input_hex: c2 05 57
old 1: select uf_dec('&input_hex') from dual
new 1: select uf_dec('c2 05 57') from dual
UF_DEC('C20557')
----------------
486
本例中idx_t1_id索引中,共4个extent,共32个block,
1个branch block,23个leaf block,通过dump这32个block可知,
每个索引段的前3个block是metadata block，第4个block是branch block,其它的block是leaf block。在assm类型的表空间中,
segment的extent是按64k,1m,8m这样的算法增长的,当65k的增长到148个extent之后,就开始增长1m的extent,
当1m的增长够420之后,
就开始分配8m的extent,这样会避开大segment分配过多的extent。
SQL> select count(*) as totals,blocks
from dba_extents where segment_name='RESELLER_LOG' group by blocks;
TOTALS BLOCKS
---------- ----------
148
8
420128
12 1024
该索引IDX_T1_ID的branch block的中的大致内容:
=10507
block addr:0x14001bc file_id 5 block_id 444
SQL> select to_number('01bc','xxxx') from dual;
TO_NUMBER('01BC','XXXX')
------------------------
444
------------------------
[/php]
|
