數據庫索引的作用(數據庫索引有什么作用)

問題1. 數據庫為什么要設計索引?

圖書館存了1000W本圖書,要從中找到《架構師之路》,一本本查,要查到什么時候去?

于是,圖書管理員設計了一套規則:

(1)一樓放歷史類,二樓放文學類,三樓放IT類…

(2)IT類,又分軟件類,硬件類…

(3)軟件類,又按照書名排序…

以便快速找到一本書。

與之類比,數據庫存儲了1000W條數據,要從中找到name=”shenjian”的記錄,一條條查,要查到什么時候去?

于是,要有索引,用于提升數據庫的查找速度。

問題2. 哈希(hash)比樹(tree)更快,索引結構為什么要設計成樹型?

加速查找速度的數據結構,常見的有兩類:

(1)哈希,例如HashMap,查詢/插入/修改/刪除的平均時間復雜度都是O(1);

(2)樹,例如平衡二叉搜索樹,查詢/插入/修改/刪除的平均時間復雜度都是O(lg(n));

可以看到,不管是讀請求,還是寫請求,哈希類型的索引,都要比樹型的索引更快一些,那為什么,索引結構要設計成樹型呢?

畫外音:80%的同學,面試都答不出來。

索引設計成樹形,和SQL的需求相關。

對于這樣一個單行查詢的SQL需求:

select * from t where name=”shenjian”;

確實是哈希索引更快,因為每次都只查詢一條記錄。

畫外音:所以,如果業務需求都是單行訪問,例如passport,確實可以使用哈希索引。

但是對于排序查詢的SQL需求:

(1)分組:group by

(2)排序:order by

(3)比較:<、>

(4)…

哈希型的索引,時間復雜度會退化為O(n),而樹型的“有序”特性,依然能夠保持O(log(n))的高效率。

任何脫離需求的設計都是耍流氓。

多說一句,InnoDB并不支持手動建立哈希索引。

畫外音:自適應hash索引,是InnoDB內核機制。

問題3. 數據庫索引為什么使用B+樹?

為了保持知識體系的完整性,簡單介紹下幾種樹。

第一種:二叉搜索樹

二叉搜索樹,如上圖,是最為大家所熟知的一種數據結構,就不展開介紹了,它為什么不適合用作數據庫索引?

(1)當數據量大的時候,樹的高度會比較高,數據量大的時候,查詢會比較慢;

(2)每個節點只存儲一個記錄,可能導致一次查詢有很多次磁盤IO;

畫外音:這個樹經常出現在大學課本里,所以最為大家所熟知。

第二種:B樹

B樹,如上圖,它的特點是:

(1)不再是二叉搜索,而是m叉搜索;

(2)葉子節點,非葉子節點,都存儲數據;

(3)中序遍歷,可以獲得所有節點;

畫外音,實在不想介紹這個特性:非根節點包含的關鍵字個數j滿足,(┌m/2┐)-1 <= j <= m-1,節點分裂時要滿足這個條件。

B樹被作為實現索引的數據結構被創造出來,是因為它能夠完美的利用“局部性原理”。

什么是局部性原理?

局部性原理的邏輯是這樣的:

(1)內存讀寫塊,磁盤讀寫慢,而且慢很多;

(2)磁盤預讀:磁盤讀寫并不是按需讀取,而是按頁預讀,一次會讀一頁的數據,每次加載更多的數據,如果未來要讀取的數據就在這一頁中,可以避免未來的磁盤IO,提高效率;

畫外音:通常,操作系統一頁數據是4K,MySQL的一頁是16K。

(3)局部性原理:軟件設計要盡量遵循“數據讀取集中”與“使用到一個數據,大概率會使用其附近的數據”,這樣磁盤預讀能充分提高磁盤IO;

B樹為何適合做索引?

(1)由于是m分叉的,高度能夠大大降低;

(2)每個節點可以存儲j個記錄,如果將節點大小設置為頁大小,例如4K,能夠充分的利用預讀的特性,極大減少磁盤IO;

第三種:B+樹

B+樹,如上圖,仍是m叉搜索樹,在B樹的基礎上,做了一些改進:

(1)非葉子節點不再存儲數據,數據只存儲在同一層的葉子節點上;

畫外音:B+樹中根到每一個節點的路徑長度一樣,而B樹不是這樣。

(2)葉子之間,增加了鏈表,獲取所有節點,不再需要中序遍歷;

這些改進讓B+樹比B樹有更優的特性:

(1)范圍查找,定位min與max之后,中間葉子節點,就是結果集,不用中序回溯;

畫外音:范圍查詢在SQL中用得很多,這是B+樹比B樹最大的優勢。

(2)葉子節點存儲實際記錄行,記錄行相對比較緊密的存儲,適合大數據量磁盤存儲;非葉子節點存儲記錄的PK,用于查詢加速,適合內存存儲;

(3)非葉子節點,不存儲實際記錄,而只存儲記錄的KEY的話,那么在相同內存的情況下,B+樹能夠存儲更多索引;

最后,量化說下,為什么m叉的B+樹比二叉搜索樹的高度大大大大降低?

大概計算一下:

(1)局部性原理,將一個節點的大小設為一頁,一頁4K,假設一個KEY有8字節,一個節點可以存儲500個KEY,即j=500;

(2)m叉樹,大概m/2<= j <=m,即可以差不多是1000叉樹;

(3)那么:

一層樹:1個節點,1*500個KEY,大小4K

二層樹:1000個節點,1000*500=50W個KEY,大小1000*4K=4M

三層樹:1000*1000個節點,1000*1000*500=5億個KEY,大小1000*1000*4K=4G

畫外音:額,幫忙看下有沒有算錯。

可以看到,存儲大量的數據(5億),并不需要太高樹的深度(高度3),索引也不是太占內存(4G)。

總結

(1)數據庫索引用于加速查詢;

(2)雖然哈希索引是O(1),樹索引是O(log(n)),但SQL有很多“有序”需求,故數據庫使用樹型索引;

(3)InnoDB不支持手動創建哈希索引;

(4)數據預讀的思路是:磁盤讀寫并不是按需讀取,而是按頁預讀,一次會讀一頁的數據,每次加載更多的數據,以便未來減少磁盤IO

(5)局部性原理:軟件設計要盡量遵循“數據讀取集中”與“使用到一個數據,大概率會使用其附近的數據”,這樣磁盤預讀能充分提高磁盤IO

(5)數據庫的索引最常用B+樹:

- 很適合磁盤存儲,能夠充分利用局部性原理,磁盤預讀;

- 很低的樹高度,能夠存儲大量數據;

- 索引本身占用的內存很小;

- 能夠很好的支持單點查詢,范圍查詢,有序性查詢;

“數據庫索引有什么作用”的內容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業相關的知識可以關注本站網站,小編將為大家輸出更多高質量的實用文章!