問答專欄Q & A COLUMN
相信很多程序員朋友對(duì)數(shù)據(jù)的索引并不陌生，最常見的索引是 B+ Tree 索引，索引可以加快數(shù)據(jù)庫(kù)的檢索速度，但是會(huì)降低新增、修改、刪除操作的速度，一些錯(cuò)誤的寫法會(huì)導(dǎo)致索引失效等等。
但是如果被問到，為什么用了索引之后，查詢就會(huì)變快？B+ Tree 索引的原理是什么？這時(shí)候很多人可能就不知道了，今天我就以 MySQL 的 InnoDB 引擎為例，講一講 B+ Tree 索引的原理。
MySQL 的基本存儲(chǔ)結(jié)構(gòu)是頁(yè)，大概就是這個(gè)樣子的：
在這里，我們需要了解以下幾點(diǎn)（非常重要）：
當(dāng)我們用 MySQL 的 InnoDB 引擎創(chuàng)建表，有且只能有一個(gè)主鍵；如果我們沒有顯示地指定之間，那么MySQL 會(huì)自動(dòng)生成一個(gè)隱含字段作為主鍵；
聚集索引：以主鍵創(chuàng)建的索引；聚集索引的葉子節(jié)點(diǎn)存儲(chǔ)的是表中的數(shù)據(jù)；
非聚集索引：非主鍵創(chuàng)建的索引；非聚集索引在葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵和索引列；使用非聚集索引查詢數(shù)據(jù)，會(huì)查詢到葉子上的主鍵，再根據(jù)主鍵查到數(shù)據(jù)（這個(gè)過程叫做回表）。
我們以聚集索引做講解，頁(yè)和頁(yè)之間、以及頁(yè)和數(shù)據(jù)之間的關(guān)系是這樣的：
數(shù)據(jù)頁(yè)和數(shù)據(jù)頁(yè)之間，組成一個(gè)雙向鏈表；
每個(gè)數(shù)據(jù)頁(yè)中的記錄，是一個(gè)單向鏈表；
每個(gè)數(shù)據(jù)頁(yè)都根據(jù)內(nèi)部的記錄生成一個(gè)頁(yè)目錄（Page directory），如果是主鍵的話，可以在頁(yè)目錄中使用二分法快速定位；
如果我們根據(jù)一個(gè)非主鍵、非索引列進(jìn)行查詢，那么需要遍歷雙向鏈表，找到所在的頁(yè)；再遍歷頁(yè)內(nèi)的單向鏈表；如果表內(nèi)數(shù)據(jù)很大的話，這樣的查詢就會(huì)很慢。
先讓我們看看 B+ Tree 索引大概是什么樣子（以聚集/主鍵索引為例）：
假如這時(shí)候我們要查詢 id = 16 的數(shù)據(jù)：
查詢頁(yè)-1，找到頁(yè)-2 存儲(chǔ)的是小于 30 的數(shù)據(jù)；
查詢頁(yè)-2，找到頁(yè)-5 存儲(chǔ)的是 10~20 的數(shù)據(jù)；
查詢頁(yè)-5，找到 id = 16 的數(shù)據(jù)。
很顯然，沒有用索引的時(shí)候，需要遍歷雙向鏈表來定位對(duì)應(yīng)的頁(yè)，而有了索引，則可以通過一層層“目錄”定位到對(duì)應(yīng)的頁(yè)上。
B+ Tree 是一顆平衡樹，如果對(duì)這顆樹新增、修改、刪除的話，會(huì)破壞它的原有結(jié)構(gòu)；
我們?cè)谧鰯?shù)據(jù)新增、修改、刪除的時(shí)候，需要花額外的時(shí)間去維護(hù)索引；
正因?yàn)檫@些額外的開銷，導(dǎo)致索引會(huì)降低新增、修改、刪除的速度。
現(xiàn)在你是否理解了 B+ Tree 索引的原理？
最后再留一個(gè)思考題：為什么官方建議使用自增長(zhǎng)主鍵作為索引？大家可以在留言中寫下你的答案。
評(píng)論0
加載中...0
回答0
回答0
回答0
回答0
回答0
回答0
回答0
回答0
回答0
回答
