關於mysql表索引方法btree的信息

本文目錄一覽：

• 1、MySQL索引的Index method中btree和hash的區別
• 2、MySQL BTREE索引
• 3、mysql btree和hash索引對比
• 4、mysql索引方法btree和hash
• 5、mysql中的索引怎樣使用btree索引

MySQL索引的Index method中btree和hash的區別

當分片索引不是純整型的字符串時，只接受整型的內置 hash 算法是無法使用的。為此，stringhash 按照用戶定義的起點和終點去截取分片索引字段中的部分字符，根據當中每個字符的二進制 unicode 值換算出一個長整型數值，然後就直接調用內置 hash 算法求解分片路由：先求模得到邏輯分片號，再根據邏輯分片號直接映射到物理分片。

用戶需要在 rule.xml 中定義 partitionLength[] 和 partitionCount[] 兩個數組和 hashSlice 二元組。

在 DBLE 的啟動階段，點乘兩個數組得到模數，也是邏輯分片的數量

並且根據兩個數組的叉乘，得到各個邏輯分片到物理分片的映射表（物理分片數量由 partitionCount[] 數組的元素值之和）

此外根據 hashSlice 二元組，約定把分片索引值中的第 4 字符到第 5 字符（字符串以 0 開始編號，編號 3 到編號 4 等於第 4 字符到第 5 字符）字符串用於 「字符串-整型」的轉換

在 DBLE 的運行過程中，用戶訪問使用這個算法的表時，WHERE 子句中的分片索引值會被提取出來，取當中的第 4 個字符到第 5 字符，送入下一步

設置一個初始值為 0 的累計值，逐個取字符，把累計值乘以 31，再把這個字符的 unicode 值當成長整型加入到累計值中，如此類推直至處理完截取出來的所有字符，此時的累計值就能夠代表用戶的分片索引值，完成了 「字符串-整型」 的轉換

對上一步的累計值進行求模，得到邏輯分片號

再根據邏輯分片號，查映射表，直接得到物理分片號

與MyCat的類似分片算法對比

請點擊輸入圖片描述

兩種算法在string轉化為int之後，和 hash 分區算法相同，區別也繼承了 hash 算法的區別。

開發注意點

【分片索引】1. 必須是字符串

【分片索引】2. 最大物理分片配置方法是，讓 partitionCount[] 數組和等於 2880

例如：

property name=”partitionLength”1/propertyproperty name=”partitionCount”2880/property

或

property name=”partitionLength”1,1/propertyproperty name=”partitionCount”1440,1440/property

【分片索引】3. 最小物理分片配置方法是，讓 partitionCount[] 數組和等於 1

例如

property name=”partitionLength”2880/propertyproperty name=”partitionCount”1/property

【分片索引】4. partitionLength 和 partitionCount 被當做兩個逗號分隔的一維數組，它們之間的點乘必須在 [1, 2880] 範圍內

【分片索引】5. partitionLength 和 partitionCount 的配置對順序敏感

property name=”partitionLength”512,256/propertyproperty name=”partitionCount”1,2/property

和

property name=”partitionLength”256,512/propertyproperty name=”partitionCount”2,1/property

是不同的分片結果

【分片索引】6. 分片索引字段長度小於用戶指定的截取長度時，截取長度會安全減少到符合分片索引字段長度

【數據分佈】1. 分片索引字段截取越長則越有利於數據均勻分佈

【數據分佈】2. 分片索引字段的內容重複率越低則越有利於數據均勻分佈

運維注意點

【擴容】1. 預先過量分片，並且不改變 partitionCount 和 partitionLength 點乘結果，也不改變截取設置 hashSlice 時，可以避免數據再平衡，只需進行涉及數據的遷移

【擴容】2. 若需要改變 partitionCount 和 partitionLength 點乘結果或改變截取設置 hashSlice 時，需要數據再平衡

【縮容】1. 預先過量分片，並且不改變 partitionCount 和 partitionLength 點乘結果，也不改變截取設置 hashSlice 時，可以避免數據再平衡，只需進行涉及數據的遷移

【縮容】2. 若需要改變 partitionCount 和 partitionLength 點乘結果或改變截取設置 hashSlice 時，需要數據再平衡

配置注意點

【配置項】1. 在 rule.xml 中，可配置項為 property name=”partitionLength”  、property name=”partitionCount” 和 property name=”hashSlice”

【配置項】2.在 rule.xml 中配置 property name=”partitionLength” 標籤

內容形式為：物理分片持有的虛擬分片數[,物理分片持有的虛擬分片數,…物理分片持有的虛擬分片數]

物理分片持有的虛擬分片數必須是整型，物理分片持有的虛擬分片數從左到右與同順序的物理分片數對應，partitionLength 和partitionCount 的點乘結果必須在 [1, 2880] 範圍內

【配置項】3. 在 rule.xml 中配置 property name=”partitionCount” 標籤內容形式為：物理分片數[,物理分片數,…物理分片數]

其中物理分片數必須是整型，物理分片數按從左到右的順序與同順序的物理分片持有的虛擬分片數對應，物理分片的編號從左到右連續遞進，partitionLength 和 partitionCount 的點乘結果必須在 [1, 2880] 範圍內

【配置項】4. partitionLength 和 partitionCount 的語義是：持有partitionLength[i] 個虛擬分片的物理分片有 partitionCount[i] 個

例如

property name=”partitionLength”512,256/propertyproperty name=”partitionCount”1,2/property

語義是持有 512 個邏輯分片的物理分片有 1 個，緊隨其後，持有 256 個邏輯分片的物理分片有 2 個

【配置項】5.partitionLength 和 partitionCount 都對書寫順序敏感，

例如

property name=”partitionLength”512,256/propertyproperty name=”partitionCount”1,2/property

分片結果是第一個物理分片持有頭512個邏輯分片，第二個物理分片持有緊接着的256個邏輯分片，第三個物理分片持有最後256個邏輯分片，相對的

property name=”partitionLength”256,512/propertyproperty name=”partitionCount”2,1/property

分片結果則是第一個物理分片持有頭 256 個邏輯分片，第二個物理分片持有緊接着的 256 個邏輯分片，第三個物理分片持有最後 512 個邏輯分片

【配置項】6.partitionLength[] 的元素全部為 1 時，這時候partitionCount 數組和等於 partitionLength 和 partitionCount 的點乘，物理分片和邏輯分片就會一一對應，該分片算法等效於直接取余

【配置項】7.在 rule.xml 中配置標籤，從分片索引字段的第幾個字符開始截取到第幾個字符：

若希望從首字符開始截取 k 個字符（ k 為正整數），配置的內容形式可以為「 0 : k 」、「 k 」或「 : k 」；

若希望從末字符開始截取 k 個字符（ k 為正整數），則配置的內容形式可以為「 -k : 0 」、「 -k 」或「 -k : 」；

若希望從頭第 m 個字符起算截取 n 個字符（ m 和 n 都是正整數），則先計算出 i = m – 1 和 j = i + n – 1，配置的內容形式為「 i : j 」；

若希望從尾第 m 個字符起算截取從尾算起的 n 個字符（ m 和 n 都是正整數），則先計算出 i = -m + n – 1，配置的內容形式可以為「 -m : i 」；

若希望不截取，則配置的內容形式可以為「 0 : 0 」、「 0 : 」、「 : 0 」或 「 : 」

MySQL BTREE索引

個人能力有限，如有錯誤請指出，共同學習。

二叉樹

B樹

B+樹

特點：

聚簇索引

二級索引

key數據存儲量估算：

若每個頁可以存1000個key，而且樹的高度是4，那麼

前提條件如下：

插入步驟

步驟一

因為索引中還沒有數據，所以此時的B+樹只有一個空的根結點，又由於一個頁只能存3個key，首先將10，20，5插入進去（實際上此步發生了3次插入），然後在頁面內做數據排序，最終結果如下圖：

步驟二：

由於根頁面已經寫滿，此時插入8，將發生分裂（根頁面分裂），大致步驟如下：

注意：在分裂過程中，根結點始終是不會變的，不管變成多大的樹，根結點的頁面號始終如一。

步驟五：

插入數據40，發現比根結點23大，找到103號頁面，發現已滿，執行分裂，分裂同上面葉子結點的分裂步驟。分裂後如圖所示：

步驟六：

繼續插入下一個數據9，因為比20小，找到101號頁面，發現已滿，需要做葉子結點分裂，如下圖：

傳統B+樹的數據刪除，一般都會有一個所謂的填充因子，來控制頁面數據的刪除比例，如果數據量小於這個填充因子所表示的數據量，就會有節點合併，這與分裂是相對應的。

InnoDB的實現與傳統B+樹算法有不同之處，InnoDB在刪除索引數據時，會先檢查當前頁剩餘的記錄數，如果只剩下一條記錄，就會直接將這個頁面從B+樹中摘除，也只有這種情況，InnoDB才會回收一個頁面，InnoDB的頁面沒有合併一說，但是對於根節點，即使索引數據全部刪除，根節點頁依然存在，只不過是以空頁的形式存在。

下面舉個例子描述索引刪除過程，前提條件與前面插入記錄時一致。

刪除數據 50

刪除過程全部結束，最終得到一個空的索引頁。

《MySQL運維內參》

B+樹動畫演示：

mysql btree和hash索引對比

只有 MEMORY 存儲引擎的表才可以選擇使用 BTREE 索引或者 HASH 索引，像我們 常用的innodb只支持btree索引 。兩種不同類型的索引各有其不同的適用範圍。

Hash索引只能用於對等比較，例如=,=（相當於=）操作符。時間複雜度是O(1)，一次查找便能定位數據，不像BTree索引需要從根節點到枝節點，最後才能訪問到頁節點這樣多次IO訪問，所以Hash在 單值查詢 下檢索效率遠高於BTree索引。

但是，事實上我們更多情況是使用btree而不是hash

HASH 索引有一些重要的特徵需要在使用的時候特別注意，如下所示。

下面我們可以進行驗證：

創建一個city_memory表，其中 country_id字段上加了 HASH索引

插入數據

1、先開看這條等值條件sql

2、那麼再來看 大於和小於條件sql

3、那麼in這種範圍條件呢？

in 條件對於hash來說是支持的，同樣btree當然也支持。而且btree索引在使用in條件找數據時相對於hash性能更好，因為rows由4變為2（說明使用btree掃描2行即可找到）證明如下：

4、 BETWEEN .. AND .. 條件呢？

BETWEEN .. AND .. 條件在 不會用到hash索引！再來看看 btree的情況：

BETWEEN .. AND .. 條件能夠使用到btree索引。

5、like 條件呢？

為了使用like條件，我們先將country_id類型改為 varchar

我們再來執行：

like條件會讓hash索引失效。我們再來看btree下的like怎樣：

好的，btree下也支持 like的不帶開頭%的訪問查詢

1、先來看hash索引支不支持排序

hash索引果然不能用在排序中，這多麼致命呀！產生了 Using filesort文件內排序。性能上是個大坑。

2、同樣，我們知道分組是要基於排序的。排序不使用索引，分組當然也不使用索引了。驗證如下：

最終不僅沒使用到索引，還產生了文件內排序和使用臨時表。

當使用 MEMORY 引擎表的時候，如果是默認創建的 HASH索引，就要注意 SQL 語句的編寫，確保可以使用上索引，如果索引字段需要 範圍查詢、排序、分組 就請使用btree索引；

mysql索引方法btree和hash

hash 索引結構的特殊性，其檢索效率非常高，索引的檢索可以一次定位，不像B-Tree 索引需要從根節點到枝節點，最後才能訪問到頁節點這樣多次的IO訪問，所以 Hash 索引的查詢效率要遠高於 B-Tree 索引。

可

能很多人又有疑問了，既然 Hash 索引的效率要比 B-Tree 高很多，為什麼大家不都用 Hash 索引而還要使用 B-Tree

索引呢？任何事物都是有兩面性的，Hash 索引也一樣，雖然 Hash 索引效率高，但是 Hash

索引本身由於其特殊性也帶來了很多限制和弊端，主要有以下這些。

（1）Hash 索引僅僅能滿足”=”,”IN”和””查詢，不能使用範圍查詢。

由於 Hash 索引比較的是進行 Hash 運算之後的 Hash 值，所以它只能用於等值的過濾，不能用於基於範圍的過濾，因為經過相應的 Hash 算法處理之後的 Hash 值的大小關係，並不能保證和Hash運算前完全一樣。

（2）Hash 索引無法被用來避免數據的排序操作。

由於 Hash 索引中存放的是經過 Hash 計算之後的 Hash 值，而且Hash值的大小關係並不一定和 Hash 運算前的鍵值完全一樣，所以數據庫無法利用索引的數據來避免任何排序運算；

（3）Hash 索引不能利用部分索引鍵查詢。

對於組合索引，Hash 索引在計算 Hash 值的時候是組合索引鍵合併後再一起計算 Hash 值，而不是單獨計算 Hash 值，所以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，Hash 索引也無法被利用。

（4）Hash 索引在任何時候都不能避免表掃描。

前面已經知道，Hash 索引是將索引鍵通過 Hash 運算之後，將 Hash運算結果的 Hash 值和所對應的行指針信息存放於一個 Hash

表中，由於不同索引鍵存在相同 Hash 值，所以即使取滿足某個 Hash 鍵值的數據的記錄條數，也無法從 Hash

索引中直接完成查詢，還是要通過訪問表中的實際數據進行相應的比較，並得到相應的結果。

（5）Hash 索引遇到大量Hash值相等的情況後性能並不一定就會比B-Tree索引高。

對於選擇性比較低的索引鍵，如果創建 Hash 索引，那麼將會存在大量記錄指針信息存於同一個 Hash 值相關聯。這樣要定位某一條記錄時就會非常麻煩，會浪費多次表數據的訪問，而造成整體性能低下。

mysql中的索引怎樣使用btree索引

B-Tree 索引是 MySQL 數據庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。不僅僅在 MySQL 中是如此，實際上在其他的很多數據庫管理系統中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因為 B-Tree 索引的存儲結構在數據庫的數據檢 索中有非常優異的表現。

一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結構來存儲的，也就是所有實際需要的數據都存放於 Tree 的 Leaf Node ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引當然，可能各種數據庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結構稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結構實際上是 B+Tree ，也就是在 B-Tree 數據結構的基礎上做了很小的改造，在每一個

Leaf Node 上面出了存放索引鍵的相關信息之外，還存儲了指向與該 Leaf Node 相鄰的後一個 LeafNode 的指針信息，這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。

在 Innodb 存儲引擎中，存在兩種不同形式的索引，一種是 Cluster 形式的主鍵索引（ Primary Key ），另外一種則是和其他存儲引擎（如 MyISAM 存儲引擎）存放形式基本相同的普通 B-Tree 索引，這種索引在 Innodb 存儲引擎中被稱為 Secondary Index 。