Oracle學(xué)習(xí)筆記（一）——B-Tree索引

丹楓無跡 2022-03-28

展開全文

https://blog.csdn.net/biww620/article/details/73003880

目錄是索引的一個最好的例子，每條目錄包含對應(yīng)章節(jié)的標(biāo)題和頁碼，類比索引的每條索引項包含了數(shù)據(jù)記錄的某些鍵值組合并包含了對應(yīng)數(shù)據(jù)塊的訪問路徑（rowid）。目錄的存在就是為了快速定位到感興趣的內(nèi)容，索引的存在也是問了加快對表數(shù)據(jù)的隨機(jī)訪問。

常常被提及的索引可能有單鍵索引、組合索引、唯一索引、B-Tree索引、位圖索引、函數(shù)索引、全局索引、局部索引等等。這里只是列舉出鏡率較高的索引類型，并沒有去做嚴(yán)格的劃分，各類型間有重疊，比如函數(shù)索引可以是B-Tree索引也可以是位圖索引。在Oracle中索引和表一樣屬于邏輯結(jié)構(gòu)中的段（segment）。每個索引都擁有獨立的結(jié)構(gòu)，無論是從物理結(jié)構(gòu)還是邏輯結(jié)構(gòu)來看與其所關(guān)聯(lián)的表完全分開，即便索引失效也不會造成原有SQL無法執(zhí)行，只是改變了執(zhí)行計劃，降低了執(zhí)行效率。

B-Tree索引
查找樹有完全二叉樹、二叉查找樹、平衡二叉樹、紅黑樹，B-Tree，B+-Tree，B*-Tree等。對于二叉樹其目的是要將查詢復(fù)雜度控制在O(lgN)以內(nèi)。（注：這里的lgN表示log2N），查詢效率與樹的高度有關(guān)。在少量數(shù)據(jù)構(gòu)造的二叉樹查詢是很高效的，但是在數(shù)據(jù)庫應(yīng)用中，數(shù)據(jù)量巨大，如果構(gòu)造二叉樹那么樹的高度將也很巨大，勢必增加讀取索引節(jié)點的I/O次數(shù)，影響查詢效率。于是B-Tree挺身而出，在很大的數(shù)據(jù)量范圍內(nèi)能夠保持B-Tree樹的層級不會增加。

圖片來自網(wǎng)絡(luò)

從上圖中可以看出在oraccle中B-Tree索引具有以下結(jié)構(gòu)特點：
B-Tree索引包含根節(jié)點（Root Node）、分支節(jié)點（Branch Node）和葉子節(jié)點（Leaf Node）。
索引樹高度一般都很低，上百億記錄的索引樹的高度也只有5，6層。
索引本身有序。葉子節(jié)點是一個雙向鏈表，因此可以按照索引的升序或降序進(jìn)行索引掃描。
索引項包含鍵值信息和ROWID。索引項由索引頭部、索引列的長度、索引值以及對應(yīng)記錄的rowid。其中唯一索引對應(yīng)的rowid是唯一的，非唯一索引對應(yīng)的rowid是可能有多個（多個rowid是有序的）。
索引列值全部為NULL的索引項是不會被記錄的。
B-Tree索引簡要分析
一、提高查詢效率
200w條記錄的表test_index_t1，查找條件col1 = 98765的記錄沒有索引的執(zhí)行計劃如下：

在test_index_t1表的col1列添加索引
create index index_col1 on test_index_t1(col1);
再次執(zhí)行查詢的執(zhí)行計劃如下：

未建立索引時執(zhí)行計劃是TABLE ACCESS FULL用時1100ms，建立索引后執(zhí)行計劃是INDEX RANGE SCAN用時90ms，效率提高了10倍以上。這里test_index_t1的數(shù)據(jù)量不大。如果是大數(shù)據(jù)量的表執(zhí)行效率的差距會更加明顯。
二、索引樹高度較低
通過以下sql可以查詢索引的統(tǒng)計信息，其中BLEVEL表示索引樹的高度，高度為BLEVEL + 1
SELECT
index_name,
blevel,
leaf_blocks,
num_rows,
distinct_keys,
clustering_factor
FROM
user_ind_statistics
WHERE
table_name = UPPER('test_index_t1');

對于200w條記錄的表test_index_t1執(zhí)行索引統(tǒng)計信息查詢后得到的結(jié)果為：

可以看出BLEVEL = 2也就是說索引樹的高度為3。構(gòu)建了記錄數(shù)分別為10條，20w條和300w條的表并建立相同的索引，索引樹高度分別為2,2,3。因此可以看出B-Tree索引的高度是比較低的，能夠在大數(shù)據(jù)量的情況下保證樹高度值很低。在通過索引執(zhí)行查詢時一個層級往往就代表一次I/O操作，因此保持索引樹高度較低對查詢性能有很大的好處。
三、索引包含鍵值
索引包含索引鍵值，單鍵或鍵組合，如果查詢所需的字段均在索引項中則可以避免回表讀數(shù)，提高查詢性能。創(chuàng)建表test_index_t1包含三個字段col1,col2,col3初始化為300w條記錄，并建立了（col1，col2）組合索引。
create index index_col1_col2 on test_index_t1(col1, col2);
1. 執(zhí)行sql
select col1 from test_index_t1 where col1 between 10 and 20;

2. 執(zhí)行sql
select col1, col2 from test_index_t1 where col1 between 10 and 20;

3. 執(zhí)行sql
select * from test_index_t1 where col1 between 10 and 20;

從上面三次查詢結(jié)果可以看出：
（1）三次執(zhí)行SQL均用到了索引INDEX_COL1_COL2，索引執(zhí)行方式為Index Range Scan
（2）第一次和第二次查詢（col1）、（col1、col2）均未回表讀數(shù)，而第三次查詢存在TABLE ACCESS BY INDEX ROWID回表讀數(shù)，原因是組合索引INDEX_COL1_COL2中不包含列col3，因此通過索引掃描得到最終記錄的rowid后還會根據(jù)rowid到表中讀取col3。
總體來看，如果所需列包含于索引中那么可以通過索引避免回表讀數(shù)從而提高查詢性能。但需要注意的是索引本身也有性能消耗，并不是包含的列越多越好。一般建議索引列不超過3個，從實際的經(jīng)驗來看5，6個也還是可以接受。
四、索引本身有序
在前面提到的索引結(jié)構(gòu)中可以看出索引葉子結(jié)點本身是按照索引鍵升序排列，相當(dāng)于一個雙向鏈表，可以進(jìn)行升序或降序掃描。刪除test_index_t1表的索引，再執(zhí)行查詢
select col1, col2 from test_index_t1 where col1 between 10 and 20 order by col1;

從執(zhí)行計劃和統(tǒng)計信息中可以看出執(zhí)行了排序過程并使用了內(nèi)存空間。給test_index_t1表col1字段加上索引后的執(zhí)行計劃如下

執(zhí)行計劃走索引后SORT ORDER BY不存在了。因此，如果因為排序?qū)е虏樵冃阅芙档涂梢钥紤]在索引中包含需要排序的列，這樣利用索引本身的有序性可以避免排序帶來的性能損耗。
五、索引不保存索引鍵值全部為NULL的記錄
這個特點跟count，sum/avg，max/min的執(zhí)行計劃息息相關(guān)，可以總結(jié)為以下兩點：
COUNT/SUM/AVG必須在索引列為非空的情況下才可以走到索引。（建表是列指定為Not Null或為主鍵或在where條件中指明為is not null）。
MIN/MAX則不會受到空值的影響，均能走到索引。
表test_index_t1有300w條記錄，在col1上建立了索引，執(zhí)行：
select count(1) from test_index_t1;

可以看出是走了全表掃描。在where條件中增加col1 is not null后的執(zhí)行計劃為：

用INDEX FAST FULL SCAN的方式使用索引INDEX_COL1。最后col1添加屬性not null后的執(zhí)行計劃為：

可以看出給列col1添加了not null屬性后執(zhí)行計劃跟在where條件中指明is not null相同。這里不再對sum/avg,min/max做驗證。
————————————————
版權(quán)聲明：本文為CSDN博主「biww620」的原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/biww620/java/article/details/73003880