730      阿裏雲  技術社區[雲棲]

輕輕揭開 b*tree 索引結構的神秘麵紗

李翔宇

雲和恩墨西區技術專家

大家好，我是雲和恩墨的技術專家李翔宇，今天要為大家分享的主題是《輕輕揭開b*tree索引結構的神秘麵紗》。

說到索引，大家應該都或多或少的了解甚至熟悉它，它是在各種數據庫中都會被提及的一種對象，主要用於加速查詢的速度（當然，對於 update 或者 delete 時的查找數據也同樣有效），所以我們一提到性能優化，往往就會想到索引。不過索引如何幫助查詢提高性能的，可能很多人就不是很清楚了。

我今天要分享的，其實並不是索引是如何提升查詢效率的，但今天所講的內容，卻對深入研究索引與性能的關係至關重要，隻有清楚了索引的結構與原理，才能真正理解索引，進而用好它。

當然，對 Oracle 索引了解的人都知道，索引有很多種，時間有限，所以我在這裏將以最為常見的 B*tree 索引為例，來簡單介紹 b*tree 索引的一些特點、使用限製和結構構成。

首先大家還是先來熟悉一下典型 B*tree 索引的結構圖：

很明顯，從圖中我們可以看到：

1. 整個索引結構由root,branch,leafblock構成。

2. 從root block到每一個leaf block的高度都是一樣的。

3. 索引條目總是是唯一的且在邏輯上是有序的。

4. 索引的掃描除了iffs(索引快速全掃描)總是單塊讀的形式。

在這裏也簡單提一句索引類型，雖然我們本次隻介紹 B*tree 索引，但也可以簡單了解一下索引類型以及相對應的數據庫版本演進：

B*tree 索引在使用時也是有一些限製的：

1. B*tree 的 level 最多為24。

2. 從 8i 以後 B*tree 索引的字段最多為32。

3. B*tree 索引的鍵值（關鍵字）在不同版本的長度限製（字節）

在了解了 B*tree 的一些特點與限製之後，我們來開始我們真正的內容，通過解剖 B*tree 的具體結構來揭開索引的麵紗。

回想剛才的結構圖，可以看到整個 B*tree 索引由 root block，branch block，leaf block 組成，那麼我們來看看這幾種塊的描述：

root block

1. Every index has one root block

2. May be a leaf block or a branch block

3. Can be an empty leaf block

4. Always the next block after the segment header in thefirst extent

總結翻譯一下就是所有索引都有且隻有1個 root block，它可以是分支塊也可以是葉子塊，甚至可以是個空的葉子快 (比如一個新建的空表上的索引)，並且總是位於第一個 extent 的段頭塊後的第一個塊，即 (HEADER_BLOCK+1)。

下麵是一個新建的表的索引樹 dump.

branch block

1. Indexes may contain branch blocks

2. Branch blocks point to other branch blocks or leafblocks

3. Branch blocks contain 0 or more rows

4. Each row has a suffix compressed key and a pointer tothe next block

5. Compressed rows are terminated with 0xFE byte

6. Each block has a pointer to the left hand side of thetree. This is part of the header

7. A branch block containing N rows points to N+1 blocks.

總結翻譯一下就是分支塊包含的每一行都有指向葉子塊/分支塊地址的指針，加上 lmc（後麵介紹） 指向的塊就是如果分支塊包含N行則會指向 N+1個快 (N>=0)，分支塊每一行裏存儲的索引鍵值可能是完整鍵值也可能是前綴 （後麵介紹）。

leaf block

1. Every index has a least one leaf block

2. Each leaf block contains 0 or more rows

3. Each row contains a key and data

4. Indexes can be unique or non-unique

5. Leaf row formats differ for unique and non-uniqueindexes

總結翻譯一下就是所有索引必須至少有1個葉子塊，且每一行包含索引鍵值和 DATA（如果是唯一索引就是 rowid，非唯一索引為null），所以說唯一索引和非唯一索引的葉子塊在結構上是不同的。

上麵都是些描述，空口白牙的一點都不直觀，那麼下麵我們通過 dump 塊結構的方法，具體來看看這些 block 到底有什麼聯係和不同。

測試步驟：

在做完上麵的 event 之後，我們可以從產生出的用戶進程跟蹤文件中看到 dump 出的索引樹信息：

----- begin tree dump branch: 0x4087b9 4229049 (0: nrow: 3,  level: 2)            --root block    branch: 0x408d67 4230503 (-1: nrow: 379, level: 1)      --branch block       leaf:  0x4087ba 4229050 (-1: nrow: 2 rrow: 2)           --leaf block       leaf:  0x408af3 4229875 (0: nrow: 2 rrow: 2)       leaf:  0x408aea 4229866 (1: nrow: 2 rrow: 2)       leaf:  0x408eec 4230892 (2: nrow: 2 rrow: 2)       ...       leaf:  0x4089a0 4229536 (376: nrow: 2 rrow: 2)       leaf:  0x408d13 4230419 (377: nrow: 2 rrow: 2)      branch: 0x408d68 4230504 (0: nrow: 620, level: 1)       --branch block       leaf:  0x408999 4229529 (-1: nrow: 2 rrow: 2)       leaf:  0x408d14 4230420 (0: nrow: 2 rrow: 2)       leaf:  0x408b92 4230034 (1: nrow: 2 rrow: 2)       ...       leaf:  0x408ee8 4230888 (617: nrow: 2 rrow: 2)       leaf:  0x408ae9 4229865 (618: nrow: 3 rrow: 3)    branch: 0x408eeb 4230891 (1: nrow: 1, level: 1)          --branch block       leaf:  0x408eea 4230890 (-1: nrow: 1 rrow: 1) ----- end tree dump

通過該 dump 我們可以得到下列信息：

root block：

1. dba=4229049 表示 root block 的數據塊地址，該塊為段頭塊後的第一個塊

SELECT header_block,        header_file,        DBMS_UTILITY.DATA_BLOCK_ADDRESS_FILE  (4229049) root_fno,        DBMS_UTILITY.DATA_BLOCK_ADDRESS_BLOCK  (4229049) root_bno   FROM dba_segments  WHERE segment_name = 'IDX_LXY_A';   HEADER_BLOCK  HEADER_FILE   ROOT_FNO   ROOT_BNO ------------ -----------  ---------- ----------        34744           1          1         34745      --ROOT_BNO=HEADER_BLOCK+1

2. level=2 表示索引層級號 (leafblock的level為0)

3. nrow=3 表示該 root block 下有3個 branch block

4. leaf block 的 nrow 表示 index entries；rrow 表示 non-deleted entris

接著是 root block 的詳細信息：

Branch block dump ================= header address 140112751121988=0x7f6e8ac25644 kdxcolev 2 KDXCOLEV Flags = - - - kdxcolok 1 kdxcoopc 0x81: opcode=1: iot flags=--- is  converted=Y kdxconco 2   kdxcosdc 2 kdxconro 2 kdxcofbo 32=0x20 kdxcofeo 6038=0x1796 kdxcoavs 6006 kdxbrlmc 4230503=0x408d67 kdxbrsno 1 kdxbrbksz 8056 kdxbr2urrc 0 row#0[8048] dba: 4230504=0x408d68 col 0; len 2; (2): 34 34         col 1; TERM                      row#1[6038] dba: 4230891=0x408eeb col 0; len 2000; (2000): 39 39 39  20...20 col 1; len 3; (3): 00 40 8f

我們重點關注其中標紅的地方。

kdxbrlmc: block address if index value is less thanthe first (row#0) value

對於該 root block 的例子意思就是如果索引鍵值小於 row#0 的 col 0，就指向在 kdxbrlmc 對應的 branch block 上，這裏即 dba=4230503。

對於該 root block 的例子(索引字段類型為char(2000)):
row#0[8048] dba: 4230504=0x408d68
col 0; len 2; (2):  34 34 –- 通過 len=2 判斷明顯是索引鍵值前綴,轉化為實際值則是'44',說明該 root block 的 lmc 指向的 branch block 的最後一個 leaf block 的最後一個索引條目的索引鍵值一定<'44'
col 1; TERM              -- 這裏無需使用 ROWID 來保證索引邏輯的順序，所以為 TERM
row#1[6038] dba: 4230891=0x408eeb
col 0; len 2000; (2000): 39 39 39 20...20 -- 通過 len=2000 判斷為完整索引鍵值，轉化為實際值則是rtrim(col 0)='999'，上一個 branch block 即 row#0 對應的 branch block 的最後一個 leafblock 的最後一條索引條目的索引鍵值一定等於'999'
col 1; len 3; (3):  00 40 8f  -- len(3) 這裏是 rowid 前綴,且上一個 branch block(row#0) 的最後一個 leaf block 的最後一條索引條目的索引鍵值的 ROWID 一定前兩位是'0040'後1位小於'8f'

下麵驗證一下剛才的結論。

該 root block 的 lmc 指向的 branchblock(dba=4230503) 的最後一個 leafblock (通過 dump 塊 4230503 得到 dba=4230419) 的最後一條索引條目的索引鍵值為：
row#1[6021] flag: ------,lock: 2, len=2011
col 0; len 2000; (2000): 34 33 39 20...20  -- 轉化為實際值為'439'後麵補位的 null 省略，'439'<'44'
col 1; len 6; (6):  0040 8c 60 00 01
row#0 對應的 branchblock(dba=4230504) 的最後一個 leaf block(dba=4229865) 的最後一條索引條目的索引鍵值為:
row#2[6021] flag: ----S-,lock: 2, len=2011
col 0; len 2000; (2000): 39 39 39 20...20 -- 轉化為實際值為'999'後麵補位的 null 省略，'999'='999'
col 1; len 6; (6):  00 40 8b 4d 00 02 -- 前兩位是'00 40'，第三位是'8b'<'8f'

和之前的結論是一致的。

其餘那些trace中的縮寫單詞的含義參考如下:

kdxcolev: index level (0 represents leaf blocks)

kdxcolok: denotes whether structural block transactionis occurring

kdxcoopc: internal operation code

kdxconco: index column count

kdxcosdc: count of index structural changes involvingblock

kdxconro: number of index entries (does not includekdxbrlmc pointer)

kdxcofbo: offset to beginning of free space withinblock

kdxcofeo: offset to the end of free space (i.e.. firstportion of block containing index data)

kdxcoavs: available space in block (effectively areabetween kdxcofbo and kdxcofeo)

kdxbrsno: last index entry to be modified

kdxbrbksz: size of usable block space

針對本例子根據上麵的分析和結論對 root block 的總結如下：

1. 該root block分別有3個branch block,順序為kdxbrlmc,row#0,row#1指向的塊。

2. 每個root block都隻有一個lmc,這個lmc指向的branchblock的最後一個leaf block的最後一條索引條目的索引鍵值一定小於等於row#0指向的branch block的第一個leaf block的第一條索引條目的索引鍵值,row#0與row#1同上

3. root block的行記錄所對應的存儲格式為:行頭 + branch block的DBA+ col 0 + col 1,其中col 0為該行行頭branchblock對應的kdxbrlmc所指向的leaf block的第一條索引條目的索引鍵值或索引鍵值前綴

col 1這裏分兩種情況：

1) 當行頭對應的 branch block 的對應的 kdxbrlmc 所指向的 leaf block 的第一條索引條目的索引鍵值>上一個 branch block 對應的最後一個 leaf block 的最後一條索引條目的索引鍵值時，此時 col 0 為該行行頭 branchblock 對應的 kdxbrlmc 所指向的 leaf block 的第一條索引條目的索引鍵值前綴，因為不需要再用 rowid 來保證索引邏輯的順序，所以此時 col 1為固定值 TERM;

2) 當行頭對應的 branch block 的對應的 kdxbrlmc 所指向的 leaf block 的第一條索引條目的索引鍵值=上一個 branch block 對應的最後一個 leaf block 的最後一條索引條目的索引鍵值時，此時 col 0 為該行行頭 branchblock 對應的 kdxbrlmc 所指向的 leaf block 的第一條索引條目的完整索引鍵值，且需要用 rowid 來保證索引邏輯的順序，此時 col 1為對應 ROWID 或 ROWID 前綴。

接下來我們看看分支塊：

root block 下共有3個 branch block：

branch: 0x408d67 4230503 (-1:nrow: 379, level: 1)  --- 1表示是 root block 的 lmc 所指向的分支塊

branch: 0x408d68 4230504 (0: nrow: 620, level: 1)  -- 對應 root block 的 row#0

branch: 0x408eeb 4230891 (1: nrow: 1, level: 1)     -- 對應 root block 的 row#1

下麵是分支塊的 trace 部分，注意看裏麵的描述信息：

Branch block dump ================= header address 140186507995716=0x7f7fb702ea44 kdxcolev 1 KDXCOLEV Flags = - - - kdxcolok 1 kdxcoopc 0x85: opcode=5: iot flags=--- is  converted=Y kdxconco 2 kdxcosdc 1 kdxconro 619 kdxcofbo 1266=0x4f2 kdxcofeo 2550=0x9f6 kdxcoavs 1284 kdxbrlmc 4229529=0x408999 kdxbrsno 616 kdxbrbksz 8056 kdxbr2urrc 0 row#0[4863] dba: 4230420=0x408d14 -- leaf block的dba col 0; len 3; (3): 34 34 30        --該 leaf block 的第一條索引條目的索引鍵值或前綴 col 1; TERM                      --當 col 0 為索引鍵值前綴時，col 1 為 TERM；當 col 0 為完整索引鍵值時 col 1 為該 leaf block 的第一條索引條目的 ROWID 或前綴 row#1[4872] dba: 4230034=0x408b92 col 0; len 3; (3): 34 34 31 col 1; TERM row#2[4881] dba: 4229537=0x4089a1 col 0; len 3; (3): 34 34 32 col 1; TERM row#3[4890] dba: 4230422=0x408d16 col 0; len 3; (3): 34 34 33 col 1; TERM ... row#617[2559] dba: 4230888=0x408ee8 col 0; len 3; (3): 39 39 37 col 1; TERM row#618[8047] dba: 4229865=0x408ae9 col 0; len 3; (3): 39 39 38 col 1; TERM

根據上麵的 trace 內容，我們可以總結一下 branch block (index 的 height=3)：

1. 該 branch block 分別有620個 leaf block

2. 每個 branch block 都隻有一個 lmc，這個 lmc 指向的 leafblock 的最後一條索引條目的索引鍵值一定小於等於 row#0 指向的 leaf block 的第一條索引條目的索引鍵值

3. branch block 的行記錄所對應的存儲格式為:行頭 + leaf block 的 DBA+ col 0 + col 1，其中 col 0 為該行行頭 leafblock 對應的的第一條索引條目的索引鍵值或索引鍵值前綴

col 1這裏也分兩種情況：

1) 當行頭對應的 leaf block 的對應的 leaf block 的第一條索引條目的索引鍵值>該 leaf block 對應 kdxleprv 所指向的 leaf block 的最後一條索引條目的索引鍵值時，此時 col 0 為該行行頭 leaf block 的第一條索引條目的索引鍵值前綴，因為不需要再用 rowid 來保證索引邏輯的順序，所以此時 col 1 為固定值 TERM;

2) 當行頭對應的 leaf block 的對應的 leaf block 的第一條索引條目的索引鍵值=該 leaf block 對應 kdxleprv 所指向的 leaf block 的最後一條索引條目的索引鍵值時，此時 col 0 為該行行頭 leaf block 的第一條索引條目的完整索引鍵值,且需要用 rowid 來保證索引邏輯的順序，此時 col 1 為對應 ROWID 或 ROWID 前綴,隻要能和 kdxleprv 所指向的葉子塊的最後一行索引行所對應的數據行的 ROWID 區分開就行，可以不是完整的 ROWID。

可以看出 branch block 和 root block 在結構上幾乎是一樣的。

最後是 Leaf block 的 trace 信息：

--row#3[4890] dba: 4230422=0x408d16 Leaf block dump =============== header address 140186507995740=0x7f7fb702ea5c kdxcolev 0 KDXCOLEV Flags = - - - kdxcolok 1 kdxcoopc 0x87: opcode=7: iot flags=--- is  converted=Y kdxconco 2 kdxcosdc 1 kdxconro 2 kdxcofbo 40=0x28 kdxcofeo 4010=0xfaa kdxcoavs 3970 kdxlespl 0 kdxlende 0 kdxlenxt 4230421=0x408d15  --指向下一個leaf block kdxleprv 4229537=0x4089a1  --指向上一個leaf block kdxledsz 0 kdxlebksz 8032 row#0[4010] flag: ----S-, lock: 2, len=2011 col 0; len 2000; (2000): 34 34 33 20 ... 20 col 1; len 6; (6): 00 40 8a 14 00 01 row#1[6021] flag: ------, lock: 2, len=2011 col 0; len 2000; (2000): 34 34 33 20 ... 20 col 1; len 6; (6): 00 40 8c 61 00 02

上麵那些 trace 中的縮寫單詞的含義參考如下:

1. kdxlespl: bytes of uncommitted data at time of blocksplit that have been cleaned out

2. kdxlende: number of deleted entries

3. kdxlenxt: pointer to the next leaf block in the indexstructure via corresponding rba

4. kdxleprv: pointer to the previous leaf block in theindex structure via corresponding rba

5. Kdxledsz: deleted space

6. kdxlebksz: usable block space (by default less thanbranch due to the additional ITL entry)

我們可以總結一下 leaf block:

1. leaf block 是沒有 lmc 的，所有的葉子塊由 kdxleprv 和 kdxlenxt 串聯起來形成一個鏈表。所以才有索引範圍掃描一說。如果 kdxlenxt=0 則說明該葉子塊為最後一個葉子塊，如果 kdxleprv=0 則說明該葉子塊為第一個葉子塊。

2. 葉子塊的每一行對應一個索引條目，包含了索引鍵值和 rowid (其中唯一索引和非唯一索引有一些區別)。

3. 如果一條 row 被刪除，記錄將會從 leaf block 去刪去，flag 標記為D，如：

row#0[2205] flag: ---D--,  lock: 44, len=17  D：表示該條索引條目已經被刪除 col 0; len 7; (7):   78 74 04 08 11 07 35    col 1; len 6; (6):   1f 62 38 b2 00 2f

如果一個 leaf block 被完全清空，該塊會被放到 freelist 裏，已供重新使用。可以通過10224事件去驗證。

4. 即使一個分支塊下的葉子塊的記錄被完全清空，分支塊並不會更新或者做任何標記來說明該葉子塊裏的記錄被完全刪除，下次定位時仍然會掃描這些空的葉子塊。如對一個高度為3的索引做一個min/max操作，在索引沒有任何碎片的情況下，隻需要3次邏輯讀即可完成，分別為1個root，1個branch，1個 leaf。

但是當索引將左邊大部分的葉子塊的記錄全部刪除後，隻有最右邊的葉子塊存在記錄，這時去做min操作會出現下麵的情況(仍然會讀取空的葉子塊，定位路線為root block的lmc定位到branch block，再由branch block的lmc定位到leafblock，之後進行範圍掃描一直到找到第一條記錄後為止)。

邏輯讀高達 24295。

好了，到目前為止，我們已經把索引的基本結構摸清楚了，那麼在這個基礎上，讓我們再多看一些，多想一些。比如：唯一索引和非唯一索引在結構上有什麼區別呢？

其實唯一索引和非唯一索引的 root block 和 branchblock 結構基本是一樣的,例如，我們來借用引用之前 dump 出的非唯一索引 trace 來進行分析。

非唯一索引的 branch block 如下：

Branch block dump ================= header address 140186507995716=0x7f7fb702ea44 kdxcolev 1 KDXCOLEV Flags = - - - kdxcolok 1 kdxcoopc 0x85: opcode=5: iot flags=--- is  converted=Y kdxconco 2 kdxcosdc 1 kdxconro 619 kdxcofbo 1266=0x4f2 kdxcofeo 2550=0x9f6 kdxcoavs 1284 kdxbrlmc 4229529=0x408999 kdxbrsno 616 kdxbrbksz 8056 kdxbr2urrc 0 row#0[4863] dba: 4230420=0x408d14 col 0; len 3; (3): 34 34 30 col 1; TERM row#1[4872] dba: 4230034=0x408b92 col 0; len 3; (3): 34 34 31 col 1; TERM row#2[4881] dba: 4229537=0x4089a1 col 0; len 3; (3): 34 34 32 col 1; TERM row#3[4890] dba: 4230422=0x408d16 col 0; len 3; (3): 34 34 33 col 1; TERM ... row#617[2559] dba: 4230888=0x408ee8 col 0; len 3; (3): 39 39 37 col 1; TERM row#618[8047] dba: 4229865=0x408ae9 col 0; len 3; (3): 39 39 38 col 1; TERM

而唯一索引的 branch block 如下：

Branch block dump ================= header address  140045722856004=0x7f5eef902a44 kdxcolev 1 KDXCOLEV Flags = -  - - kdxcolok 0 kdxcoopc 0x80:  opcode=0: iot flags=--- is converted=Y kdxconco 1 kdxcosdc 0 kdxconro 33 kdxcofbo 94=0x5e kdxcofeo  7828=0x1e94 kdxcoavs 7734 kdxbrlmc  4229050=0x4087ba kdxbrsno 0 kdxbrbksz 8056 kdxbr2urrc 0 row#0[8049] dba:  4229051=0x4087bb col 0; len 2; (2):  31 31 row#1[8042] dba:  4229052=0x4087bc col 0; len 2; (2):  31 34 row#2[8035] dba:  4229053=0x4087bd col 0; len 2; (2):  31 37 row#3[8029] dba:  4229054=0x4087be col 0; len 1; (1):  32 ... col 0; len 2; (2):  39 33 row#31[7835] dba:  4229106=0x4087f2 col 0; len 2; (2):  39 36 row#32[7828] dba:  4229107=0x4087f3 col 0; len 2; (2):  39 39

通過對比不難發現：

唯一索引的 root block 和 branch block 的 kdxconco 總比非唯一索引的 root block 和 branch block 的 kdxconco 少1，因為唯一索引的 root block 和 branchblock 不需要存儲 rowid 或 rowid 前綴。

那麼進一步來看看 leaf block 會不會不同。

非唯一索引的 leaf block 如下：

Leaf block dump =============== header address 140186507995740=0x7f7fb702ea5c kdxcolev 0 KDXCOLEV Flags = - - - kdxcolok 1 kdxcoopc 0x87: opcode=7: iot flags=--- is  converted=Y kdxconco 2 kdxcosdc 1 kdxconro 2 kdxcofbo 40=0x28 kdxcofeo 4010=0xfaa kdxcoavs 3970 kdxlespl 0 kdxlende 0 kdxlenxt 4230421=0x408d15 kdxleprv 4229537=0x4089a1 kdxledsz 0   --bytes in ROWID data kdxlebksz 8032 row#0[4010] flag: ----S-, lock: 2, len=2011 col 0; len 2000; (2000): 34 34 33 20 ... 20 col 1; len 6; (6): 00 40 8a 14 00 01 row#1[6021] flag: ------, lock: 2, len=2011 col 0; len 2000; (2000): 34 34 33 20 ... 20 col 1; len 6; (6): 00 40 8c 61 00 02

唯一索引的 leaf block 如下:

Leaf block dump =============== header address 140045722856028=0x7f5eef902a5c kdxcolev 0 KDXCOLEV Flags = - - - kdxcolok 0 kdxcoopc 0x80: opcode=0: iot flags=--- is  converted=Y kdxconco 1 kdxcosdc 0 kdxconro 3 kdxcofbo 42=0x2a kdxcofeo 2002=0x7d2 kdxcoavs 1960 kdxlespl 0 kdxlende 0 kdxlenxt 4229104=0x4087f0 kdxleprv 4229094=0x4087e6 kdxledsz 6   --bytes in ROWID data kdxlebksz 8032 row#0[6022] flag: ------, lock: 0, len=2010, data:(6): 00 40 87 ee 00 00 –rowid col 0; len 2000; (2000): 38 38 20..20 row#1[4012] flag: ------, lock: 0, len=2010,  data:(6): 00 40 87 ee 00 01 col 0; len 2000; (2000): 38 39 20..20 row#2[2002] flag: ------, lock: 0, len=2010,  data:(6): 00 40 87 b3 00 02 col 0; len 2000; (2000): 39 20 20 20

通過對比可以清楚的看到：

1. 唯一索引的 leaf block 的 kdxconco 總比非唯一索引的 leaf block 的 kdxconco 少1，因為索引條目必須是唯一的，所以對於非唯一索引的索引條目=索引鍵值 +rowid，需要多加一列 rowid 才能保證索引條目唯一；而唯一索引的索引條目=索引鍵值，ROWID 是存儲在DATA裏的。

2. 唯一索引的每一行總比非唯一索引少1個字節，所以唯一索引會比非唯一索引更節約存儲空間，但是節約得很少很少。

今天的分享就到這裏，希望通過對這次分享能讓大家更加了解 B*tree 索引，從而在 SQL 優化中能更靈活的使用它。謝謝。

問題：btree b+tree b*tree 有什麼區別麼？以前看資料說 b+是葉子結點多了指向其他節點的指針，b*是不僅葉子結點，分支結點也多了指針，不知道是不是這麼簡單。

回複：b tree 是2叉樹，比如我們的排序使用的就是2叉樹，所以這種結構是有序的。但是不平衡。後來有了 b-tree 這裏是平衡樹的意思，這種結構是有序且平衡的，但是葉子塊並沒有如 kdxleprv 和 kdxlenxt 這樣的指針。b+tree 是在 b-tree 的基礎上為葉子塊之間增加了鏈表指針如 kdxleprv 和 kdxlenxt雙向的鏈表指針。b*tree 是在 b+tree 的基礎上為分支塊之間也增加了鏈表指針。

最後更新：2017-07-18 20:36:02

  上一篇：  深入剖析 ORA-04031 的前世今生

  下一篇：  SQL性能突然降低引起的業務辦理緩慢案例一則