'「轉」數據庫索引,到底是什麼做的?'

"

問題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需求:

  • 分組:group by
  • 排序:order by
  • 比較:<、>

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

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

多說一句,InnoDB並不支持哈希索引。

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

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

第一種:二叉搜索樹

"

問題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需求:

  • 分組:group by
  • 排序:order by
  • 比較:<、>

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

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

多說一句,InnoDB並不支持哈希索引。

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

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

第一種:二叉搜索樹

「轉」數據庫索引,到底是什麼做的?


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

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

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

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

第二種:B樹

"

問題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需求:

  • 分組:group by
  • 排序:order by
  • 比較:<、>

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

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

多說一句,InnoDB並不支持哈希索引。

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

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

第一種:二叉搜索樹

「轉」數據庫索引,到底是什麼做的?


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

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

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

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

第二種:B樹

「轉」數據庫索引,到底是什麼做的?


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

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

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

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

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

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

什麼是局部性原理?

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

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

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

畫外音:通常,一頁數據是4K。

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

B樹為何適合做索引?

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

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

第三種:B+樹

"

問題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需求:

  • 分組:group by
  • 排序:order by
  • 比較:<、>

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

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

多說一句,InnoDB並不支持哈希索引。

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

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

第一種:二叉搜索樹

「轉」數據庫索引,到底是什麼做的?


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

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

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

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

第二種:B樹

「轉」數據庫索引,到底是什麼做的?


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

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

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

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

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

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

什麼是局部性原理?

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

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

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

畫外音:通常,一頁數據是4K。

(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)。

總結

  • 數據庫索引用於加速查詢
  • 雖然哈希索引是O(1),樹索引是O(log(n)),但SQL有很多“有序”需求,故數據庫使用樹型索引
  • InnoDB不支持哈希索引
  • 數據預讀的思路是:磁盤讀寫並不是按需讀取,而是按頁預讀,一次會讀一頁的數據,每次加載更多的數據,以便未來減少磁盤IO
  • 局部性原理:軟件設計要儘量遵循“數據讀取集中”與“使用到一個數據,大概率會使用其附近的數據”,這樣磁盤預讀能充分提高磁盤IO
  • 數據庫的索引最常用B+樹:

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

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

(3)索引本身佔用的內存很小;

(4)能夠很好的支持單點查詢,範圍查詢,有序性查詢;

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

轉自微信公眾號 架構師之路

"

相關推薦

推薦中...