共計(jì) 2564 個(gè)字符，預(yù)計(jì)需要花費(fèi) 7 分鐘才能閱讀完成。
自動(dòng)寫代碼機(jī)器人，免費(fèi)開通
這篇文章主要介紹了 mysql 的索引底層之實(shí)現(xiàn)原理是什么，具有一定借鑒價(jià)值，需要的朋友可以參考下。希望大家閱讀完這篇文章后大有收獲。下面讓丸趣 TV 小編帶著大家一起了解一下。
MySQL 索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理
一、定義
索引定義：索引（Index）是幫助 MySQL 高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。
本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)。
二、B-Tree
m 階 B -Tree 滿足以下條件：
1、每個(gè)節(jié)點(diǎn)至多可以擁有 m 棵子樹。
2、根節(jié)點(diǎn)，只有至少有 2 個(gè)節(jié)點(diǎn)（要么極端情況，就是一棵樹就一個(gè)根節(jié)點(diǎn)，單細(xì)胞生物，即是根，也是葉，也是樹)。
3、非根非葉的節(jié)點(diǎn)至少有的 Ceil(m/2)個(gè)子樹(Ceil 表示向上取整，如 5 階 B 樹，每個(gè)節(jié)點(diǎn)至少有 3 個(gè)子樹，也就是至少有 3 個(gè)叉)。
4、非葉節(jié)點(diǎn)中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中 n 表示該節(jié)點(diǎn)中保存的關(guān)鍵字個(gè)數(shù)，K 為關(guān)鍵字且 Ki Ki+1，A 為指向子樹根節(jié)點(diǎn)的指針。
5、從根到葉子的每一條路徑都有相同的長(zhǎng)度（葉子節(jié)點(diǎn)在相同的層）
B-Tree 特性：
1、關(guān)鍵字集合分布在整顆樹中；
2、任何一個(gè)關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)節(jié)點(diǎn)中；
3、每個(gè)節(jié)點(diǎn)存儲(chǔ) date 和 key；
4、搜索有可能在非葉子節(jié)點(diǎn)結(jié)束；
5、一個(gè)節(jié)點(diǎn)中的 key 從左到右非遞減排列；
6、所有葉節(jié)點(diǎn)具有相同的深度，等于樹高 h。
B-Tree 上查找算法的偽代碼如下：
三、B+Tree
B+Tree 與 B -Tree 的差異在于：
1、B+Tree 非葉子節(jié)點(diǎn)不存儲(chǔ) data，只存儲(chǔ) key；
2、所有的關(guān)鍵字全部存儲(chǔ)在葉子節(jié)點(diǎn)上；
3、每個(gè)葉子節(jié)點(diǎn)含有一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針，帶順序訪問指針的 B + 樹提高了區(qū)間查找能力；
4、非葉子節(jié)點(diǎn)可以看成索引部分，節(jié)點(diǎn)中僅含有其子樹（根節(jié)點(diǎn)）中的最大（或最小）關(guān)鍵字；
四、B/B+ 樹索引的性能分析
依據(jù)：使用磁盤 I / O 次數(shù)評(píng)價(jià)索引結(jié)構(gòu)的優(yōu)劣
主存和磁盤以頁為單位交換數(shù)據(jù)，將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁，因此每個(gè)節(jié)點(diǎn)只需一次 I / O 就可以完全載入。
根據(jù) B 樹的定義，可知檢索一次最多需要訪問 h 個(gè)節(jié)點(diǎn)
漸進(jìn)復(fù)雜度:O(h)=O(logdN)
dmax=floor(pagesize/(keysize+datasize+pointsize))
一般實(shí)際應(yīng)用中，出度 d 是非常大的數(shù)字，通常超過 100，因此 h 非常小（通常不超過 3，3 層可存大約一百萬數(shù)據(jù)）
B-Tree 中一次檢索最多需要 h - 1 次 I /O（根節(jié)點(diǎn)常駐內(nèi)存）
B+Tree 內(nèi)節(jié)點(diǎn)不含 data 域，因此出度 d 更大，則 h 更小，I/ O 次數(shù)少，效率更高，故 B +Tree 更適合外存索引。
五、MySQL 索引實(shí)現(xiàn)
1、MyISAM 引擎使用 B +Tree 作為索引結(jié)構(gòu)，葉節(jié)點(diǎn)的 data 域存放的是數(shù)據(jù)記錄的地址；
MyISAM 主索引和輔助索引在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求 key 是唯一的，而輔助索引的 key 可以重復(fù)；
2、InnoDB 的數(shù)據(jù)文件本身就是索引文件，葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄，這種索引叫做聚集索引。
因?yàn)?InnoDB 的數(shù)據(jù)文件本身要按主鍵聚集，所以 InnoDB 要求表必須有主鍵（MyISAM 可以沒有），如果沒有顯式指定，則 MySQL 系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵，如果不存在這種列，則 MySQL 自動(dòng)為 InnoDB 表生成一個(gè)隱含字段作為主鍵。
InnoDB 的輔助索引 data 域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址；
輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄；
3、頁分裂問題
如果主鍵是單調(diào)遞增的，每條新記錄會(huì)順序插入到頁，當(dāng)頁被插滿后，繼續(xù)插入到新的頁；
如果寫入是亂序的，InnoDB 不得不頻繁地做頁分裂操作，以便為新的行分配空間。頁分裂會(huì)導(dǎo)致移動(dòng)大量數(shù)據(jù)，一次插入最少需要修改三個(gè)頁而不是一個(gè)頁。
如果頻繁的頁分裂，頁會(huì)變得稀疏并被不規(guī)則地填充，所以最終數(shù)據(jù)會(huì)有碎片。
六、總結(jié)
了解不同存儲(chǔ)引擎的索引實(shí)現(xiàn)方式對(duì)于正確使用和優(yōu)化索引都非常有幫助
1、為什么不建議使用過長(zhǎng)的字段作為主鍵？
2、為什么選擇自增字段作為主鍵？
3、為什么常更新是字段不建議建立索引？
4、為什么選擇區(qū)分度高的列作為索引？區(qū)分度的公式是 count(distinct col)/count(*)
5、盡可能的使用覆蓋索引
七、優(yōu)化 LIMIT 分頁查詢
SELECT * FROM table where condition LIMIT offset , rows ;上述 SQL 語句的實(shí)現(xiàn)機(jī)制是：
1、從“table”表中讀取 offset+rows 行記錄。
2、拋棄前面的 offset 行記錄，返回后面的 rows 行記錄作為最終的結(jié)果。
覆蓋索引：
select a.id, sid, parent_s_id from cashpool_account_relationship a join (select id from cashpool_account_relationship LIMIT 1000000,10)b on a.id = b.id;
select id, sid, parent_s_id from cashpool_account_relationship where id =(select id from cashpool_account_relationship LIMIT 1000000,1) LIMIT 10;
八、Q A
1、InnoDB 支持 hash 索引嗎？– 馬欣
InnoDB 是支持 hash 索引的，不過其支持的 hash 索引是自適應(yīng)的，InnoDB 存儲(chǔ)引擎會(huì)根據(jù)表的使用情況自動(dòng)為表生成 hash 索引，不能人為干預(yù)是否在一張表中生成 hash 索引。
2、InnoDB 主鍵索引的葉節(jié)點(diǎn)含完整的數(shù)據(jù)記錄，那主鍵索引文件要比數(shù)據(jù)文件大嗎？– 徐財(cái)厚
1）. 在 Innodb 引擎中，主鍵索引中的葉子結(jié)點(diǎn)包含記錄數(shù)據(jù)，主鍵索引文件即為數(shù)據(jù)文件。
2）. 在 tables 表中統(tǒng)計(jì)的 data_length 數(shù)據(jù)為主鍵索引大小，index_length 為統(tǒng)計(jì)的這個(gè)表中所有輔助索引（二級(jí)索引）索引的大小。
感謝你能夠認(rèn)真閱讀完這篇文章，希望丸趣 TV 小編分享 mysql 的索引底層之實(shí)現(xiàn)原理是什么內(nèi)容對(duì)大家有幫助，同時(shí)也希望大家多多支持丸趣 TV，關(guān)注丸趣 TV 行業(yè)資訊頻道，遇到問題就找丸趣 TV，詳細(xì)的解決方法等著你來學(xué)習(xí)!
向 AI 問一下細(xì)節(jié)丸趣 TV 網(wǎng) – 提供最優(yōu)質(zhì)的資源集合！
