當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

Oracle B-Tree Index 原理

發(fā)布時(shí)間：2023/12/9 编程问答 29 豆豆

生活随笔收集整理的這篇文章主要介紹了 Oracle B-Tree Index 原理小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

一. B-Tree Index 原理

官網(wǎng)說(shuō)明：

?????? No index structure can satisfy all needs, but the self-balancing B-tree index comes closest to optimizing the performance of searches on large sets of data. Each B-tree node holds multiple keys and pointers. The maximum number of keys in a node supported by a specific B-tree is the order of that tree. Each node has a potential of order+1 pointers to the level below it.

?????? For example, the order=2 B-tree illustrated in Figure 7-1 has tree pointers: to child nodes whose value is less than the first key, to the child nodes whose value is greater than the first key and less than the second key, and to the child nodes whose value is greater than the second key. Thus, the B-tree algorithm minimizes the number of reads and writes necessary to locate a record by passing through fewer nodes than in a binary tree algorithm, which has only one key and at most two children for each decision node. Here we describe the Knuth variation in which the index consists of two parts: a sequence set that provides fast sequential access to the data, and an index set that provides direct access to the sequence set.

?????? Although the nodes of a B-tree generally do not contain the same number of data values, and they usually contain a certain amount of unused space, the B-tree algorithm ensures that the tree remains balanced and that the leaf nodes are at the same level.

?????? Oracle中的Btree Index具有3大結(jié)構(gòu)，root節(jié)點(diǎn)，branch節(jié)點(diǎn)，leaf節(jié)點(diǎn). Root節(jié)點(diǎn)始終緊跟索引段頭.? 當(dāng)索引比較小的時(shí)候，root節(jié)點(diǎn)，branch節(jié)點(diǎn)，leaf節(jié)點(diǎn)都存儲(chǔ)在同一個(gè)block中.

?????? Branch節(jié)點(diǎn)主要存儲(chǔ)了索引的鍵值,但是這個(gè)鍵值并不是完整的，它只是完整索引值的部分前綴.同時(shí)Branch節(jié)點(diǎn)還存儲(chǔ)了指向leaf節(jié)點(diǎn)的指針(DBA)，另外有個(gè)主意的是branch節(jié)點(diǎn)中還有個(gè)叫kdxbrlmc的指針.

Oracle rdba和 dba 說(shuō)明

http://blog.csdn.net/tianlesoftware/archive/2011/06/07/6529346.aspx

?????? Leaf節(jié)點(diǎn)主要存儲(chǔ)了完整的索引鍵值，以及相關(guān)索引鍵值的部分rowid(這個(gè)rowid去掉了data object number部分)，同時(shí)leaf 節(jié)點(diǎn)還存儲(chǔ)了2個(gè)指針(DBA)，他們分別指向上一個(gè)leaf節(jié)點(diǎn)以及下一個(gè)leaf節(jié)點(diǎn).?

?????? Btree Index 是始終平衡的，也就是說(shuō) 從Root節(jié)點(diǎn)到 Leaf 節(jié)點(diǎn)的任何一個(gè)路徑都是等距離的.?

????? Btree Index 默認(rèn)是按照索引值升序排列的，當(dāng)然了我們可以在創(chuàng)建/重建的時(shí)候設(shè)置它降序排列.?

?????? Index Scan 的時(shí)候，采用的是 sequential read,并且一次只能讀一個(gè)block(INDEX FAST FULL SCAN 除外).??

?????? Btree Index Update的時(shí)候，先做的是 delete,然后進(jìn)行insert.?

?????? Btree Index 不存儲(chǔ) Null值，但是如果組合索引其中一列是非Null的，那么組合索引也會(huì)存儲(chǔ)Null值.?

二. Tree Index 存儲(chǔ)原理?

2.1 創(chuàng)建測(cè)試數(shù)據(jù)

SYS@anqing2(rac2)> select * from v$version where rownum=1;

BANNER

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

Oracle Database 10g Enterprise Edition Release 10.2.0.4.0 - Prod

SYS@anqing2(rac2)> create table te as select * from? dba_objects;

Table created.

SYS@anqing2(rac2)> select count(*) from te;

? COUNT(*)

----------

?? 50258

SYS@anqing2(rac2)> insert into te select * from dba_objects;

50258 rows created.

SYS@anqing2(rac2)> commit;

Commit complete.

SYS@anqing2(rac2)> select count(*) from te;

? COUNT(*)

----------

??? 100516

SYS@anqing2(rac2)> create index idx_te_object_name on te(object_name);

Index created.

2.2 查看索引的Blevel, 可以通過(guò)DBA_INDEXES.Blevel獲得

*-Tree level: depth of the index from its root block to its leaf blocks. A depth of 0 indicates that the root block and leaf block are the same.?

?????? --從 root block 到 leaf block的深度. 如果root block 和 leaf block在同一個(gè)塊中那么 Blevel=0

SYS@anqing2(rac2)> select index_name,blevel from dba_indexes where index_name='IDX_TE_OBJECT_NAME';

INDEX_NAME???????????????????????? BLEVEL

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

IDX_TE_OBJECT_NAME????????????????????? 2

2.3 查看索引的height，索引的高度等于Blevel+1，height可以通過(guò)INDEX_STATS獲得

SYS@anqing2(rac2)> select name,height from index_stats where name='IDX_TE_OBJECT_NAME';

no rows selected

--- index_stats需要 analyze ... validate structure 收集一下，否則無(wú)數(shù)據(jù)?

SYS@anqing2(rac2)>? analyze index IDX_TE_OBJECT_NAME validate structure;

Index analyzed.

SYS@anqing2(rac2)> select name,height from index_stats where name='IDX_TE_OBJECT_NAME';

NAME?????????????????????????????? HEIGHT

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

IDX_TE_OBJECT_NAME????????????????????? 3

2.4 dump index

?????? Oracle 提供了分析 Btree index 結(jié)構(gòu)的命令 treedump，在進(jìn)行treedump之前需要獲得索引的object_id

SYS@anqing2(rac2)> select object_id from dba_objects where object_name='IDX_TE_OBJECT_NAME' and owner='SYS';?

?OBJECT_ID

----------

???? 54769???

SYS@anqing2(rac2)> oradebug setmypid

Statement processed.

SYS@anqing2(rac2)> alter session set events 'immediate trace name treedump level 54769';?

Session altered.

SYS@anqing2(rac2)> oradebug tracefile_name

/u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc

2.5 查看 treedump trace 文件?

[oracle@rac2 ~]$ cat /u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc

/u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc

Oracle Database 10g Enterprise Edition Release 10.2.0.4.0 - Production

With the Partitioning, Real Application Clusters, OLAP, Data Mining

and Real Application Testing options

ORACLE_HOME = /u01/app/oracle/product/10.2.0/db_1

System name:??? Linux

Node name:????? rac2

Release:??????? 2.6.18-194.el5

Version:??????? #1 SMP Tue Mar 16 21:52:43 EDT 2010

Machine:??????? i686

Instance name: anqing2

Redo thread mounted by this instance: 2

Oracle process number: 29

Unix process pid: 3865, image: oracle@rac2 (TNS V1-V3)

*** 2011-06-27 13:15:00.375

*** ACTION NAME:() 2011-06-27 13:15:00.371

*** MODULE NAME:(sqlplus@rac2 (TNS V1-V3)) 2011-06-27 13:15:00.371

*** SERVICE NAME:(SYS$USERS) 2011-06-27 13:15:00.371

*** SESSION ID:(130.55497) 2011-06-27 13:15:00.371

----- begin tree dump

branch: 0x4117c2 4265922 (0: nrow: 2, level: 2)

?? branch: 0x412086 4268166 (-1: nrow: 250, level: 1)

??? ??leaf: 0x4117c3 4265923 (-1: nrow: 182 rrow: 182)

????? leaf: 0x4117c4 4265924 (0: nrow: 182 rrow: 182)

????? leaf: 0x4117c5 4265925 (1: nrow: 186 rrow: 186)

????? leaf: 0x4117c6 4265926 (2: nrow: 189 rrow: 189)

????? leaf: 0x4117c7 4265927 (3: nrow: 186 rrow: 186)

????? leaf: 0x4117c8 4265928 (4: nrow: 190 rrow: 190)

????? leaf: 0x4117c9 4265929 (5: nrow: 186 rrow: 186)

????? leaf: 0x4117ca 4265930 (6: nrow: 178 rrow: 178)

????? leaf: 0x4117cb 4265931 (7: nrow: 187 rrow: 187)

????? leaf: 0x4117cc 4265932 (8: nrow: 182 rrow: 182)

?? ??????? ......

????? leaf: 0x412080 4268160 (244: nrow: 222 rrow: 222)

????? leaf: 0x412081 4268161 (245: nrow: 201 rrow: 201)

????? leaf: 0x412082 4268162 (246: nrow: 240 rrow: 240)

????? leaf: 0x412083 4268163 (247: nrow: 226 rrow: 226)

????? leaf: 0x412084 4268164 (248: nrow: 211 rrow: 211)

?? branch: 0x41227b 4268667 (0: nrow: 245, level: 1)

????? leaf: 0x412085 4268165 (-1: nrow: 229 rrow: 229)

????? leaf: 0x412087 4268167 (0: nrow: 218 rrow: 218)

????? leaf: 0x412088 4268168 (1: nrow: 231 rrow: 231)

????? leaf: 0x412109 4268297 (2: nrow: 249 rrow: 249)

??? ??......

????? leaf: 0x412278 4268664 (241: nrow: 191 rrow: 191)

????? leaf: 0x412279 4268665 (242: nrow: 180 rrow: 180)

????? leaf: 0x41227a 4268666 (243: nrow: 56 rrow: 56)

----- end tree dump

2.6 解釋 treedump 輸出?

?????? branch 表示的是 branch block ，它后面跟了一個(gè)十六進(jìn)制表示的DBA(data block address)，以及用10進(jìn)制表示的DBA 。

?????? DBA 之后表示在同一層次的相對(duì)位置(root 從0開(kāi)始,branch 以及leaf從 -1開(kāi)始)?

?????? nrow? 表示塊中包含了多少條目(包括delete的條目)?

?????? rrow? 表示塊中包含的實(shí)際條目(不包括delete的條目)?

?????? level 表示從該block到leaf的深度(leaf沒(méi)有 level)?

2.6.1? branch: 0x4117c2 4265922 (0: nrow: 2, level: 2) 說(shuō)明

?????? 這個(gè) branch block 的 level 為2，也就是說(shuō) 從這個(gè)branch block 到 leaf block 的深度為2,根據(jù)前面的查詢(xún)，這個(gè)索引的Blevel為2,所以這個(gè)branch其實(shí)是 root block. 其實(shí)根據(jù) nrow:2 也可以看出來(lái)它是root block，因?yàn)?/span>nrow:2 說(shuō)明它只包含了2個(gè)條目，那么這2個(gè)條目其實(shí)就是dump 文件中的其他2個(gè) branch block 的條目?

?????? 現(xiàn)在我來(lái)驗(yàn)證一下 branch: 0x4117c2 4265922 (0: nrow: 2, level: 2) 是不是 root block , 我查詢(xún)這個(gè) branch 的 DBA 。

SYS@anqing2(rac2)> select dbms_utility.data_block_address_file('4265922') FILE_ID,? dbms_utility.data_block_address_block('4265922') BLOCK_ID from dual;

?? FILE_ID?? BLOCK_ID

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

???????? 1????? 71618

Btree 索引的 root block總是segment header+1,所以我查詢(xún)?cè)撍饕亩晤^?

SYS@anqing2(rac2)> select header_file,header_block from dba_segments where segment_name='IDX_TE_OBJECT_NAME';?

HEADER_FILE HEADER_BLOCK

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

????????? 1??????? 71617

?????? 那么現(xiàn)在已經(jīng)證明了 branch: 0x4117c2 4265922 (0: nrow: 2, level: 2) 是root block, 其實(shí) treedump第一個(gè) branch block 就是 root block。

2.6.2 ?branch: 0x412086 4268166 (-1: nrow: 250, level: 1)? 說(shuō)明

?????? 這個(gè)branch 的 DBA為0x412086 (十六進(jìn)制)，4268166 (十進(jìn)制) ，-1 表示它是與它在同一個(gè)深度的 branch block中的第一個(gè) branch block。?

?????? nrow: 250 ：表示它有247個(gè) leaf block.

?????? level: 1 ：表示這個(gè) branch block 到 leaf block的深度為1?

2.6.3 leaf: 0x4117c3 4265923 (-1: nrow: 182 rrow: 182) ?說(shuō)明

?????? leaf 表示它是一個(gè) leaf block 0x4117c3 4265923 分別是這個(gè) leaf block 的十六進(jìn)制/十進(jìn)制的DBA.

?????? ?-1 表示它是 leaf block 中的第一個(gè) block?

?????? nrow: 182 表示它一共有182條記錄

?????? rrow: 182 表示它實(shí)際有182條記錄?

2.7? branch block dump?

?????? 這里選擇dump branch: branch: 0x412086 4268166 (-1: nrow: 250, level: 1)

SYS@anqing2(rac2)> select dbms_utility.data_block_address_file('4268166') FILE_ID,? dbms_utility.data_block_address_block('4268166') BLOCK_ID from dual;?

?? FILE_ID?? BLOCK_ID

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

???????? 1????? 73862

SYS@anqing2(rac2)> oradebug tracefile_name

/u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc

-- 先清空一下

[oracle@rac2 ~]$ cat /dev/null > /u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc

SYS@anqing2(rac2)> alter system dump datafile 1 block 73862;?

System altered.

2.7.1 部分 DUMP 文件?

[oracle@rac2 ~]$ cat /u01/app/oracle/admin/anqing/udump/anqing2_ora_3865.trc? ??????????

*** 2011-06-27 14:35:54.038

Start dump data blocks tsn: 0 file#: 1 minblk 73862 maxblk 73862

buffer tsn: 0 rdba: 0x00412086 (1/73862)

scn: 0x0000.004e24ec seq: 0x02 flg: 0x04 tail: 0x24ec0602

frmt: 0x02 chkval: 0x3371 type: 0x06=trans data

Hex dump of block: st=0, typ_found=1

Dump of memory from 0x0E707400 to 0x0E709400

E707400 0000A206 00412086 004E24EC 04020000? [..... A..$N.....]

......

E7093F0 00000000 00000000 00000000 24EC0602? [...............$]

Block header dump:? 0x00412086

?Object id on Block? Y

?seg/obj: 0xd5f1? csc: 0x00.4e24c9? itc: 1? flg: -? typ: 2 - INDEX

???? fsl: 0? fnx: 0x0 ver: 0x01

?Itl?????????? Xid????????????????? Uba???????? Flag? Lck??????? Scn/Fsc

0x01?? 0xffff.000.00000000? 0x00000000.0000.00? C---??? 0? scn 0x0000.004e24c9

Branch block dump

=================

header address 242250820=0xe707444

kdxcolev 1

KDXCOLEV Flags = - - -

kdxcolok 0

kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y

kdxconco 2

kdxcosdc 0

kdxconro 249

kdxcofbo 526=0x20e

kdxcofeo 557=0x22d

kdxcoavs 31

kdxbrlmc 4265923=0x4117c3

kdxbrsno 0

kdxbrbksz 8056

kdxbr2urrc 0

row#0[8023] dba: 4265924=0x4117c4

col 0; len 24; (24):

?2f 31 30 64 65 32 32 63 36 5f 43 6c 61 73 73 54 79 70 65 49 6d 70 6c 32

col 1; len 3; (3):? 00 41 1b

row#1[7984] dba: 4265925=0x4117c5

col 0; len 30; (30):

?2f 31 31 64 35 30 39 31 32 5f 44 61 74 65 46 6f 72 6d 61 74 5a 6f 6e 65 44

?61 74 61 5f 7a

col 1; len 3; (3):? 00 41 1c

row#2[7973] dba: 4265926=0x4117c6

col 0; len 5; (5):? 2f 31 32 61 32

col 1; TERM

row#3[7931] dba: 4265927=0x4117c7

col 0; len 30; (30):

?2f 31 33 38 35 32 32 37 66 5f 4d 61 70 52 65 67 69 6f 6e 43 6f 6e 74 61 69

?6e 6d 65 6e 74

col 1; len 6; (6):? 00 41 18 d5 00 08

......

row#247[571] dba: 4268163=0x412083

col 0; len 6; (6):? 41 4c 4c 5f 45 56

col 1; TERM

row#248[557] dba: 4268164=0x412084

col 0; len 8; (8):? 41 4c 4c 5f 4d 50 5f 50

col 1; TERM

----- end of branch block dump -----

End dump data blocks tsn: 0 file#: 1 minblk 73862 maxblk 73862

[oracle@rac2 ~]$

2.7.2解釋部分dump輸出?

kdxcolev 1? --該block到leaf block的深度(leaf block 為0).這里branch block 的level 為1 與前面查詢(xún)相吻合??

KDXCOLEV Flags = - - -?

kdxcolok 0? --表示是否有事務(wù)lock了這個(gè)branch block，如果有，有多少事務(wù)?

kdxcoopc 0x80: opcode=0: iot flags=--- is converted=Y?

kdxconco 2? --索引值條目. 這里表示有2個(gè)條目?

kdxcosdc 0? --這個(gè)block的結(jié)構(gòu)被更改次數(shù).這里0表示沒(méi)有更改?

kdxconro 249 --索引條目(不包含kdxbrlmc 指針)?

kdxcofbo 526=0x20e? --空閑空間的起始偏移量

kdxcofeo 557=0x22d? --空閑空間的末尾偏移量

kdxcoavs 31? --block中的空閑空間=kdxcofeo-kdxcofbo?

kdxbrlmc 4265923=0x4117c3 --如果index value小于row#0，指向該 block 的地址?

kdxbrsno 0?? --最后被更改的索引條目?

kdxbrbksz 8056 --塊中的可用空間?

kdxbr2urrc 0?

row#0[8023] dba: 4265924=0x4117c4 --row# 表示索引條目數(shù)，從0開(kāi)始，緊接著就是十進(jìn)制和十六進(jìn)制的DBA，該DBA指向 leaf block?

col 0; len 24; (24): --列的行號(hào)，從0開(kāi)始，緊接著的就是列的長(zhǎng)度以及列的值，那么這個(gè)值稱(chēng)之為separator key,這個(gè)separator key 可以區(qū)分真實(shí)的索引值，所以從這里我們也知道 branch block不會(huì)存儲(chǔ)完整的索引值，只要能區(qū)分就行?

?2f 31 30 64 65 32 32 63 36 5f 43 6c 61 73 73 54 79 70 65 49 6d 70 6c 32

col 1; len 3; (3):? 00 41 1b

2.8 ?leaf block DUMP?

?????? 這里選擇 row#247[571] dba: 4268163=0x412083, 因?yàn)樗乃饕I很少?

row#247[571] dba: 4268163=0x412083

col 0; len 6; (6):? 41 4c 4c 5f 45 56

col 1; TERM

dump 之前先看一下? row#247[571] 存儲(chǔ)的 ' 41 4c 4c 5f 45 56' 是什么索引鍵. 使用如下代碼轉(zhuǎn)換：

SQL> set serveroutput on

/* Formatted on 2011/6/27 16:53:27 (QP5 v5.163.1008.3004) */

DECLARE

?? n?? VARCHAR2 (2000);

BEGIN

?? DBMS_STATS.convert_raw_value ('41', n);