oracle B*Tree索引的了解

1 索引的root, brance和leaf

1.1 建立表, 索引, 新增資料

SQL> create tablespace ASSM datafile '/oradata/ltest/assm.dbf' size 10m autoextend on segment space management auto;

Tablespace created

SQL> create tablespace ASSM_INDEX datafile '/oradata/ltest/assm_index.dbf' size 10m autoextend on segment space management auto;

SQL> create table t(x char(1024)) tablespace assm;

Table created

SQL> create index ti on t(x) tablespace assm_index;

Index created

SQL> insert into t values(1);

1 row inserted

SQL> commit;

Commit complete

1.2 dump索引資料

SQL> select file_id, extent_id, block_id, blocks

2 from dba_extents

3 where segment_name = 'TI';

FILE_ID EXTENT_ID BLOCK_ID BLOCKS

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

10 0 9 8

因為位圖塊是9和10，段頭塊是11，是以dump的塊要是12。

SQL> alter system dump datafile 10 block 12;

System altered

Trace資訊如下：

row#0[6997] flag: ------, lock: 2, len=1035

col 0; len 1024; (1024): '下面是indexed data value(1024Byte)，第一個31代表1'

31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

…… 剩下的都是20，即是空格。共1023個空格。

col 1; len 6; (6): 01 c0 00 10 00 00 '這個值是對應row在表中的RowID(6Byte)'

1.3 索引資料驗證

利用dbms_rowid包從到資料的FILE#和BLOCK。

SQL> select a.*,

2 rowid,

3 dbms_rowid.rowid_object(rowid) obj#,

4 dbms_rowid.rowid_relative_fno(rowid) file#,

5 dbms_rowid.rowid_block_number(rowid) block#,

6 dbms_rowid.rowid_row_number(rowid) row#

7 from t a;

X ROWID OBJ# FILE# BLOCK# ROW#

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

1 AAANC3AAHAAAAAQAAA 53431 7 16 0

通過DUMP中資訊，得到索引資訊01 c0 00 10 00 00。取前4個位元組計算FILE#和BLOCK#。後2個位元組是用來算ROW#的。

SQL> select dbms_utility.data_block_address_file(to_number('01c00010', 'xxxxxxxx')) file#,

2 dbms_utility.data_block_address_block(to_number('01c00010', 'xxxxxxxx')) block#

3 from dual;

FILE# BLOCK#

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

7 16

驗證：索引資訊指向對應資料行。（ROW#明顯是一樣的，就不驗證了）

1.4 計算索引塊能存儲的資料行

index leaf note包含很多的index entry (也就是row), 每個entry有5個columns：

row header(3Byte) | length(1 Byte) | indexed data value(1024 Byte) | length(1 Byte) | RowID(6 Byte)

這樣每個row的大小為：3 + 1 + 1024 + 1 + 6=1035 Byte。

db_block_size=8192，block的預設pct_free=10%，是以每個block能存儲7個rows:

SQL> select 8192*0.9/1035 from dual;

8192*0.9/1035

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

7.12347826086

1.5 繼續插入資料

繼續插入資料

SQL> insert into t values(10);

SQL> insert into t values(2);

SQL> insert into t values(3);

SQL> insert into t values(4);

SQL> insert into t values(5);

SQL> insert into t values(6);

SQL> analyze index ti validate structure;

Index analyzed

SQL> select btree_space, used_space, pct_used, blocks, lf_blks, br_blks

2 from index_stats;

BTREE_SPACE USED_SPACE PCT_USED BLOCKS LF_BLKS BR_BLKS

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

7996 6222 78 8 1 0

隻有一個leaf note,也就是root, 沒有更多的branch note

1.6 dump索引資料

row#0[6997] flag: ------, lock: 0, len=1035

col 0; len 1024; (1024):

31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '31代表1'

……

col 1; len 6; (6): 01 c0 00 10 00 00

row#1[5962] flag: ------, lock: 0, len=1035

31 30 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '31 30代表10'

col 1; len 6; (6): 01 c0 00 10 00 01

row#2[4927] flag: ------, lock: 2, len=1035

32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '32代表2'

col 1; len 6; (6): 01 c0 00 10 00 02

row#3[3892] flag: ------, lock: 2, len=1035

33 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '33代表3'

col 1; len 6; (6): 01 c0 00 10 00 03

row#4[2857] flag: ------, lock: 2, len=1035

34 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '34代表4'

col 1; len 6; (6): 01 c0 00 10 00 04

row#5[1822] flag: ------, lock: 2, len=1035

35 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '35代表5'

col 1; len 6; (6): 01 c0 00 10 00 05

row#6[787] flag: ------, lock: 2, len=1035

36 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '36代表6'

col 1; len 6; (6): 01 c0 00 10 00 06

1.7 第一個索引塊滿後，再插入資料

SQL> insert into t values(7);

24020 8305 35 8 2 1

發現BTREE_SPACE的值是3個blocks的大小了，其中有2個是leaf notes，1個是branch note，也就是root，它單獨占一個block；因為這兩個leaf notes不能隻是獨自地排列在那裡，是以有了上一層的branch(root) note來管理他們；如果你仔細一點會發現，這個root占用的block是最開始的那個leaf占用的block 12，并不是為它新開辟了一個block，而是将原來那個leaf 中的entries轉移到後面的block(13)中去了。同時新插入的第8行index entry，放在了新的block 14中去了。之是以将第一個leaf轉移到後面的block，而将這個block作為root，是因為root的資訊儲存在資料字典中，修改資料字典的代價相比移動leaf要大一些。

1.8 驗證上面的結論

row#0[8049] dba: 41943054=0x280000e

col 0; len 1; (1): 37 '--37代表7，即最大值'

col 1; TERM

SQL> alter system dump datafile 10 block 13;

row#0[787] flag: ------, lock: 0, len=1035

row#1[1822] flag: ------, lock: 0, len=1035

31 30 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

row#2[2857] flag: ------, lock: 0, len=1035

32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

row#3[3892] flag: ------, lock: 0, len=1035

33 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

row#4[4927] flag: ------, lock: 0, len=1035

34 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

row#5[5962] flag: ------, lock: 0, len=1035

35 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

row#6[6997] flag: ------, lock: 0, len=1035

36 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

觀察trace檔案，發現row的順序沒有變，但是實體偏移量正好和原來相反了，應該是轉移這個塊的結果。移動前：

row#0[6997] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 1

row#1[5962] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 10

row#2[4927] flag: ------, lock: 2, len=1035 col 0; len 1024; (1024): 2

row#3[3892] flag: ------, lock: 2, len=1035 col 0; len 1024; (1024): 3

row#4[2857] flag: ------, lock: 2, len=1035 col 0; len 1024; (1024): 4

row#5[1822] flag: ------, lock: 2, len=1035 col 0; len 1024; (1024): 5

row#6[787] flag: ------, lock: 2, len=1035 col 0; len 1024; (1024): 6

移動後：

row#0[787] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 1

row#1[1822] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 10

row#2[2857] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 2

row#3[3892] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 3

row#4[4927] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 4

row#5[5962] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 5

row#6[6997] flag: ------, lock: 0, len=1035 col 0; len 1024; (1024): 6

SQL> alter system dump datafile 10 block 14;

37 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20

col 1; len 6; (6): 01 c0 00 0c 00 00

2 索引的分裂

如果一個leaf block已經滿了（例如block 12），此時又産生了新的entry，按照他的indexed value應該插入到block 13當中，分析一下這種情況：

此時block 13中的值是：1，10，2，3，4，5，6

因為是index 是char資料類型，如果再插入一行41，按照char的排序規則，41應該插入到4和5之間。這種情況下，會将block 13中的内容分裂成兩部分，41資料後的entry将移到一個新的block中去。這樣的話，應該是：

block 12: root

block 13: 1，10，2，3，4，41

block 14: 7

block 15: 5，6

2.1 插入資料，引用索引分裂

SQL> insert into t values(41);

32016 9351 30 8 3 1

此時4個blocks，1個root，3個leaf。

2.2 Dump索引資料塊，驗證

row#0[1822] flag: ------, lock: 0, len=1035

row#1[2857] flag: ------, lock: 0, len=1035

row#2[3892] flag: ------, lock: 0, len=1035

row#3[4927] flag: ------, lock: 0, len=1035

row#4[5962] flag: ------, lock: 0, len=1035

row#5[6997] flag: ------, lock: 2, len=1035

34 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '34 31代表41'

col 1; len 6; (6): 01 c0 00 0c 00 01

SQL> alter system dump datafile 10 block 15;

row#0[5962] flag: ------, lock: 0, len=1035

row#1[6997] flag: ------, lock: 0, len=1035

3 索引的重用

所謂重用，是對row 的重用，而不是對row所在實體存儲（或說實體位置）的重用。索引是按照indexed value對row進行排序的。有新的row被插入，首先按照value排序，将他放在合适的row list中，如果他的位置正好原來有個row被删掉了，則重用這個row在row list中的位置。但是實體存儲是依次向下開辟的。看看下面這個例子，删除4，插入31，31重用了原來4在row list中的位置，但是實體存儲是新開辟的:

3.1 删資料

SQL> delete t where x = 4;

1 row deleted

3.2 Dump資料塊

Trace資訊如下

row#4[5962] flag: ---D--, lock: 2, len=1035 '有D，表示删除'

row#5[6997] flag: ------, lock: 0, len=1035

3.3 插入資料

SQL> insert into t values(31);

3.4 再Dump資料塊

31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '31代表1'

31 30 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '31 30代表10'

32 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '32代表2'

33 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '33代表3'

row#4[787] flag: ------, lock: 2, len=1035

33 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '33 31代表31, 重用了原來4在row list 中的位置，但是實體存儲是新的787，原來是5962'

col 1; len 6; (6): 01 c0 00 0c 00 02

34 31 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 '34 31代表41'

本文轉自 wws5201985 51CTO部落格，原文連結：http://blog.51cto.com/wws5201985/737012，如需轉載請自行聯系原作者

oracle B*Tree索引的了解

繼續閱讀

LoadRunner 的多種Vuser類型

華為筆試軟體

性能測試（并發負載壓力）測試分析－簡要篇

項目管理那些事兒

OS --written test1

OS-written test2

壓縮編碼M-JPEG、MPEG4、H.264

賦予使用者dba權限--解釋以上：

轉詳解C#資料庫存取圖檔三大方式

Oracle的基本操作

為什麼要選擇UniDAC

BMP檔案結構及圖像每行位元組計算方法

磁盤結構及在Linux中的命名

windows不能在本地計算機上運作oracleDbConsoleorcl

SQL語言基礎：常用的資料查詢語句

Oracle 批量查詢傳入List 傳回List