索引是什么意思

關(guān)注：23 發(fā)布時(shí)間：2022-02-08 19:25:01

相信很多程序員朋友都很熟悉數(shù)據(jù)索引。比較常見(jiàn)的索引是b樹(shù)索引，可以加快數(shù)據(jù)庫(kù)的檢索速度，但是會(huì)降低添加、修改、刪除操作的速度，一些寫(xiě)錯(cuò)會(huì)導(dǎo)致索引失效。

但是如果問(wèn)，為什么使用索引后查詢(xún)更快？b樹(shù)指數(shù)的原理是什么？這個(gè)時(shí)候很多人可能還不知道。我就以mysql innodb引擎為例，談?wù)刡樹(shù)索引的原理。

索引基礎(chǔ)知識(shí)

mysql的基本存儲(chǔ)結(jié)構(gòu)是page，大概是這樣的：

在這里，我們需要了解以下幾點(diǎn)（非常重要）：

當(dāng)我們使用mysql innodb引擎創(chuàng)建一個(gè)表時(shí)，主鍵只能有一個(gè)；如果我們不明確指定介于，mysql會(huì)自動(dòng)生成一個(gè)隱式字段作為主鍵。

聚集索引：用主鍵創(chuàng)建的索引；聚集索引的葉節(jié)點(diǎn)將數(shù)據(jù)存儲(chǔ)在表中；

非聚集索引：由非主鍵創(chuàng)建的索引；非聚集索引在葉節(jié)點(diǎn)存儲(chǔ)主鍵和索引列。使用非聚集索引查詢(xún)數(shù)據(jù)會(huì)查詢(xún)?nèi)~子上的主鍵，然后根據(jù)主鍵查找數(shù)據(jù)(這個(gè)過(guò)程稱(chēng)為返回表)。

頁(yè)面與頁(yè)面之間以及頁(yè)面與數(shù)據(jù)之間的關(guān)系

我們用聚集索引來(lái)解釋?zhuān)?yè)面和頁(yè)面之間，以及頁(yè)面和數(shù)據(jù)之間的關(guān)系如下：

數(shù)據(jù)頁(yè)之間形成雙向鏈表。

每個(gè)數(shù)據(jù)頁(yè)中的記錄都是單向鏈表；

每個(gè)數(shù)據(jù)頁(yè)根據(jù)內(nèi)部記錄生成一個(gè)頁(yè)面目錄。如果是主鍵，可以通過(guò)二分法在頁(yè)面目錄中快速定位；

如果我們按照一個(gè)非主鍵、非索引的列進(jìn)行查詢(xún)，需要遍歷雙向鏈表才能找到頁(yè)面；遍歷頁(yè)面中的單向鏈表；如果表中的數(shù)據(jù)很大，這樣的查詢(xún)會(huì)很慢。

二叉樹(shù)索引的原理

我們先來(lái)看看b樹(shù)索引是什么樣子的(以集群/主鍵索引為例):

如果我們此時(shí)要查詢(xún)id=16的數(shù)據(jù)：

查詢(xún)page -1，發(fā)現(xiàn)page -2存儲(chǔ)的數(shù)據(jù)小于30；

查詢(xún)第2頁(yè)，發(fā)現(xiàn)第5頁(yè)存儲(chǔ)了10~20個(gè)數(shù)據(jù)；

查詢(xún)第5頁(yè)，找到id=16的數(shù)據(jù)。