[[428230]]

本文轉(zhuǎn)載自微信公眾號(hào)「運(yùn)維開(kāi)發(fā)故事」，作者老鄭。轉(zhuǎn)載本文請(qǐng)聯(lián)系運(yùn)維開(kāi)發(fā)故事公眾號(hào)。

概述

索引是對(duì)數(shù)據(jù)庫(kù)表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)，使用索引可快速訪問(wèn)數(shù)據(jù)庫(kù)表中的特定信息。

索引數(shù)據(jù)結(jié)構(gòu)

二叉樹(shù)

二叉樹(shù)(binary tree)是指樹(shù)中節(jié)點(diǎn)的度不大于 2 的有序樹(shù)，它是一種最簡(jiǎn)單且最重要的樹(shù)。二叉樹(shù)的遞歸定義為：二叉樹(shù)是一棵空樹(shù)，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的，分別稱作根的左子樹(shù)和右子樹(shù)組成的非空樹(shù);左子樹(shù)和右子樹(shù)又同樣都是二叉樹(shù)

對(duì)于數(shù)組 {1,2,3,4,5} 數(shù)據(jù)結(jié)構(gòu)將成為了鏈表

特點(diǎn)：

• 父節(jié)點(diǎn)下面有兩個(gè)子節(jié)點(diǎn)。
• 右邊節(jié)點(diǎn)的數(shù)據(jù)大于左邊節(jié)點(diǎn)的數(shù)據(jù)。

二叉樹(shù).png

紅黑樹(shù)

紅黑樹(shù)是一種特定類型的二叉樹(shù)，它是在計(jì)算機(jī)科學(xué)中用來(lái)組織數(shù)據(jù)比如數(shù)字的塊的一種結(jié)構(gòu)。若一棵二叉查找樹(shù)是紅黑樹(shù)，則它的任一子樹(shù)必為紅黑樹(shù)。

紅黑樹(shù)是一種平衡二叉查找樹(shù)的變體，它的左右子樹(shù)高差有可能大于 1，所以紅黑樹(shù)不是嚴(yán)格意義上的平衡二叉樹(shù)(AVL)，但對(duì)之進(jìn)行平衡的代價(jià)較低， 其平均統(tǒng)計(jì)性能要強(qiáng)于 AVL 。

由于每一棵紅黑樹(shù)都是一棵二叉排序樹(shù)，因此，在對(duì)紅黑樹(shù)進(jìn)行查找時(shí)，可以采用運(yùn)用于普通二叉排序樹(shù)上的查找算法，在查找過(guò)程中不需要顏色信息。

紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)如下圖：

紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu).png

特點(diǎn)：

• 紅黑樹(shù)是每個(gè)結(jié)點(diǎn)都帶有顏色屬性的二叉查找樹(shù)，顏色或紅色或黑色。
• 結(jié)點(diǎn)是紅色或黑色。
• 根結(jié)點(diǎn)是黑色。
• 所有葉子都是黑色。(葉子是NIL結(jié)點(diǎn))
• 每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色結(jié)點(diǎn))
• 從任一節(jié)結(jié)點(diǎn)其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)。
• 這些約束強(qiáng)制了紅黑樹(shù)的關(guān)鍵性質(zhì): 從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)。結(jié)果是這個(gè)樹(shù)大致上是平衡的。因?yàn)椴僮鞅热绮迦搿h除和查找某個(gè)值的最壞情況時(shí)間都要求與樹(shù)的高度成比例，這個(gè)在高度上的理論上限允許紅黑樹(shù)在最壞情況下都是高效的，而不同于普通的二叉查找樹(shù)。
• 是性質(zhì)4導(dǎo)致路徑上不能有兩個(gè)連續(xù)的紅色結(jié)點(diǎn)確保了這個(gè)結(jié)果。最短的可能路徑都是黑色結(jié)點(diǎn)，最長(zhǎng)的可能路徑有交替的紅色和黑色結(jié)點(diǎn)。因?yàn)楦鶕?jù)性質(zhì)5所有最長(zhǎng)的路徑都有相同數(shù)目的黑色結(jié)點(diǎn)，這就表明了沒(méi)有路徑能多于任何其他路徑的兩倍長(zhǎng)。
• 因?yàn)榧t黑樹(shù)是一種特化的二叉查找樹(shù)，所以紅黑樹(shù)上的只讀操作與普通二叉查找樹(shù)相同。

B-Tree

• 葉子結(jié)點(diǎn)具有相同的深度，葉節(jié)點(diǎn)的指針為空
• 所有元素不重復(fù)
• 節(jié)點(diǎn)中的數(shù)據(jù)索引從左到右邊遞增排列

B樹(shù)數(shù)據(jù)結(jié)構(gòu).png

B+Tree

非葉子結(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)索引(冗余)，可以存放更多的索引

葉子結(jié)點(diǎn)包含所有索引字段

葉子結(jié)點(diǎn)用指針鏈接，提高區(qū)間訪問(wèn)的性能(可以提升范圍查找的效率)

B+樹(shù)數(shù)據(jù)結(jié)構(gòu).png

特點(diǎn)關(guān)鍵字：節(jié)點(diǎn)內(nèi)有序，葉子結(jié)點(diǎn)指針鏈接，非葉子結(jié)點(diǎn)存儲(chǔ)索引(冗余)

查詢mysql 索引的數(shù)據(jù)頁(yè)的大?。?/p>

mysql> show global status like 'Innodb_page_size'; 
+------------------+-------+ 
| Variable_name    | Value | 
+------------------+-------+ 
| Innodb_page_size | 16384 | 
+------------------+-------+ 

為什么設(shè)置 16kb 呢?

Hash

• 對(duì)索引的 key 進(jìn)行一次 hash 計(jì)算就可以定位出數(shù)據(jù)存儲(chǔ)的位置
• 很多的時(shí)候 hash 索引要比 B+ 樹(shù)索引更高效
• 僅能滿足 “=” ， “in” 不支持范圍查詢
• 存在 hash 沖突問(wèn)題

Hash 數(shù)據(jù)結(jié)構(gòu).png

索引

InnoDB 索引實(shí)現(xiàn)(聚集)

• 表數(shù)據(jù)文件本身就是按 B+Tree 組織的一個(gè)索引結(jié)構(gòu)文件
• 聚集索引-葉子節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄
• 為什么 InnoDb 表必須有主鍵，并且推薦使用整型的自增主鍵?
  • 如果沒(méi)有設(shè)置索引的話，MySQL 會(huì)選擇一個(gè)數(shù)據(jù)唯一的列作為主鍵索引， 如果找不這樣的列。會(huì)去做創(chuàng)建一個(gè)隱藏列類似 rowid。
  • 表數(shù)據(jù)文件按照 B+Tree 的數(shù)據(jù)結(jié)構(gòu)維護(hù)，在葉子節(jié)點(diǎn)維護(hù)的是該行的數(shù)據(jù)。所以必須有主鍵。
  • 整型更方便 B+Tree 排序，自增的話，對(duì)于數(shù)據(jù)結(jié)構(gòu)的存放更快, 順序存放，不需要進(jìn)行大量樹(shù)的平衡操作。
• 為什么非主鍵索引結(jié)構(gòu)葉子節(jié)點(diǎn)的存儲(chǔ)的是主鍵值?
  
  • 一致性， 讓主鍵索引先成功，然后再去更新非主鍵索引關(guān)系
  • 節(jié)省存儲(chǔ)空間。
• 主鍵索引示意圖：

InnoDB 索引實(shí)現(xiàn).png

• 非主鍵索引示意圖

如果查詢的是通過(guò) name = Alice 去查詢的時(shí)候：

1. 走非主鍵索引去查詢，查詢完后拿到信息(Alice, 18)。其實(shí)這里也是一個(gè)非聚簇索引
2. 然后進(jìn)行回表查詢，再次通過(guò)主鍵去查詢做回表查詢。

兩個(gè)數(shù)據(jù)文件：

.frm 主要是存儲(chǔ)表結(jié)構(gòu)信息

.ibd 主要是存儲(chǔ)索引和數(shù)據(jù)

MyISAM 索引文件(非聚集)

• 索引文件和數(shù)據(jù)文件是分離的(非聚集)

MyISAM 存儲(chǔ)引擎索引.png

三個(gè)數(shù)據(jù)文件：

.frm 數(shù)據(jù)結(jié)構(gòu)文件

.myd 文件主要是存儲(chǔ)數(shù)據(jù)

.myi 文件主要是存儲(chǔ)索引信息

聚集索引和非聚集索引

特征：

聚集/非聚集主要是索引文件是否和數(shù)據(jù)文件在一起。

查詢效率上來(lái)說(shuō)聚集索引不會(huì)跨文件查詢效率會(huì)更加快。

聯(lián)合/復(fù)合索引

多個(gè)字段組織成一個(gè)共同的索引

組合索引.png

• 最左前綴原理為什么這樣來(lái)使用?

索引的數(shù)據(jù)是被排序的，如果跳過(guò)字段的話是無(wú)法被使用的。

示例：

where name = 'Jeff' and age = 22 -- 命中索引

where age = 30 and postatin='manager' -- 不命中索引

where postation = 'dev' -- 不命中索引

參考資料

百度百科