mysql索引概述

什么是索引

索引是一種高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),提高數(shù)據(jù)查詢效率

索引分類

從存儲(chǔ)結(jié)構(gòu)上來劃分：B-Tree，B+Tree，Hash索引

從應(yīng)用層次來分：普通索引，唯一索引，復(fù)合索引
從數(shù)據(jù)的物理順序與鍵值的邏輯（索引）順序關(guān)系：聚集索引，非聚集索引

Mysql 索引底層數(shù)據(jù)結(jié)構(gòu)選型

Hash索引介紹

hash索引基于哈希表實(shí)現(xiàn)，存儲(chǔ)引擎會(huì)對(duì)索引列使用哈希算法，計(jì)算一個(gè)哈希碼（hash code），并且將所有的哈希碼存儲(chǔ)在索引中，同時(shí)在索引表中保存指向每個(gè)數(shù)據(jù)行的指針

哈希算法也叫散列算法，就是把任意值(key)通過哈希函數(shù)變換為固定長度的 key 地址（十六進(jìn)制表示），通過這個(gè)地址進(jìn)行具體數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),哈希表是一種內(nèi)存地址映射關(guān)系

哈希索引.png

哈希表查找過程:
表中一共有 7 個(gè)數(shù)據(jù)，我們需要檢索 id=7 的數(shù)據(jù)，SQL 語法是：
select * from user where id=7; 哈希算法首先計(jì)算存儲(chǔ) id=7 的數(shù)據(jù)的物理地址 addr=hash(7)=4231，而 4231 映射的物理地址是 0x77，0x77 就是 id=7 存儲(chǔ)的數(shù)據(jù)的物理地址，通過該獨(dú)立地址可以找到對(duì)應(yīng) user_name='g'這個(gè)數(shù)據(jù)。這就是哈希算法快速檢索數(shù)據(jù)的計(jì)算過程。在查找 id=7 的數(shù)據(jù)，哈希索引只需要計(jì)算一次就可以獲取到對(duì)應(yīng)的數(shù)據(jù)，檢索速度非常快。但是 Mysql 并沒有采取哈希作為其底層算法，因?yàn)榭紤]到數(shù)據(jù)檢索有一個(gè)常用手段就是范圍查找，比如以下這個(gè) SQL 語句：select * from user where id >3;
在范圍查找過程中,簡(jiǎn)單的實(shí)現(xiàn)思路就是一次把所有數(shù)據(jù)找出來加載到內(nèi)存，然后再在內(nèi)存里篩選篩選目標(biāo)范圍內(nèi)的數(shù)據(jù)。這種查找效率低,不能對(duì)數(shù)據(jù)高效范圍查找，因此哈希索引是不適合作為 Mysql 的底層索引的數(shù)據(jù)結(jié)構(gòu)。

哈希索引.jpg

1. 哈希不支持 范圍查詢 ,不能做排序
2. mysql默認(rèn)的存儲(chǔ)引擎是Inodb,對(duì)于頻繁訪問的表，innodb會(huì)建立自適應(yīng)hash索引，即在B樹索引基礎(chǔ)上建立hash索引，可以顯著提高查找效率，對(duì)于客戶端，不可控制的，隱式的。
3. 哈希存儲(chǔ)時(shí)會(huì)降低磁盤利用率

二叉樹

演示： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

二叉樹的特點(diǎn)：

1. 一個(gè)節(jié)點(diǎn)只能有兩個(gè)子節(jié)點(diǎn)，也就是一個(gè)節(jié)點(diǎn)度不能超過2
2. 左子節(jié)點(diǎn) 小于 本節(jié)點(diǎn)，右子節(jié)點(diǎn)大于等于 本節(jié)點(diǎn)

二叉樹.jpg

在二叉樹結(jié)構(gòu)，計(jì)算比較 3 次就可以檢索到 id=7 的數(shù)據(jù)，相對(duì)于直接遍歷查詢省了一半的時(shí)間，從檢索效率上能做到高速檢索的。此外二叉樹的結(jié)構(gòu)還能提供的范圍查找功能，上圖二叉樹的葉子節(jié)點(diǎn)都是按序排列的，從左到右依次升序排列，如果我們需要找 id>5 的數(shù)據(jù)，那我們?nèi)〕龉?jié)點(diǎn)為 6 的節(jié)點(diǎn)以及其右子樹就可以了，范圍查找也是比較容易實(shí)現(xiàn)。

缺點(diǎn):
主鍵自增情況下會(huì)退化為線性鏈表，二分查找也會(huì)退化為遍歷查找（全盤掃描），檢索性能急劇下降。id主鍵索引自增情況下二叉樹已演化為線性鏈表，檢索速度降低。此時(shí)檢索 id=7 的數(shù)據(jù)的所需要計(jì)算的次數(shù)已經(jīng)變?yōu)?7 了,因此 不能直接用于實(shí)現(xiàn) Mysql 底層索引

線性鏈表.jpg

二叉查找樹存在不平衡問題，讓二叉樹始終保持基本平衡的狀態(tài)，就能保持二叉查找樹的最佳查找性能了。基于這種思路的自調(diào)整平衡狀態(tài)的二叉樹有 AVL 樹和紅黑樹。

紅黑樹

紅黑樹.jpg

上圖所示，左圖在插入數(shù)值為3時(shí)，紅黑樹的算法發(fā)現(xiàn)有偏向，就會(huì)重新調(diào)整樹結(jié)構(gòu)；調(diào)整到右邊保持平衡，如持續(xù)遞增，之前的數(shù)據(jù)1～7持續(xù)遞增的樹，會(huì)變成如下圖所示

紅黑樹遞增.jpg

遞增插入過程紅黑樹會(huì)自動(dòng)左旋右旋節(jié)點(diǎn)以及節(jié)點(diǎn)變色，調(diào)整樹的形態(tài)，使其保持基本的平衡狀態(tài)，也就保證了查找效率不會(huì)明顯減低。如上圖所示。紅黑樹下查找 id=7 的所要比較的節(jié)點(diǎn)數(shù)為 4，依然保持二叉樹不錯(cuò)的查找效率。

紅黑樹很好的解決線性鏈表問題，但紅黑樹問題也比較大。
每次插入都要檢查規(guī)則，再把樹進(jìn)行重新平衡，這個(gè)是非常消耗時(shí)間,數(shù)據(jù)量大的話，紅黑樹的深度會(huì)比較深，并且產(chǎn)生“右傾”,樹一旦深就代表著我們讀取磁盤次數(shù)就會(huì)增加，因此 不能直接用于實(shí)現(xiàn) Mysql 底層索引

紅黑樹的特點(diǎn)會(huì)自動(dòng)平衡樹，但是沒有做到絕對(duì)的平衡，會(huì)產(chǎn)生右傾

平衡二叉樹(AVL)

AVL 樹的特點(diǎn)：

1. 平衡二叉樹又稱AVL樹，在滿足二叉查找樹特性的基礎(chǔ)上，要求每個(gè)節(jié)點(diǎn)的左右子樹的高度差不能超過1。
2. 很好的查找性能，不存在極端的低效查找的情況。
3. 可以實(shí)現(xiàn)范圍查找、數(shù)據(jù)排序。

頂端的節(jié)點(diǎn)我們稱為根節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)我們稱之為葉節(jié)點(diǎn)。
平衡二叉樹和非平衡二叉樹的對(duì)比：

平衡二叉樹對(duì)比.jpg

平衡二叉樹查找過程:

平衡二叉樹查找.jpg

AVL 樹順序插入 1~16 個(gè)節(jié)點(diǎn)，查找 id=16 需要比較的節(jié)點(diǎn)數(shù)為 4。從查找效率而言，AVL 樹查找的速度要高于紅黑樹的查找效率（AVL 樹是 4 次比較，紅黑樹是 6 次比較）。從樹的形態(tài)看來，AVL 樹不存在紅黑樹的“右傾”問題。大量的順序插入不會(huì)導(dǎo)致查詢性能的降低，這從根本上解決了紅黑樹的問題。

mysql 如果使用的是 AVL 樹，我們每一個(gè)樹節(jié)點(diǎn)只存儲(chǔ)了一個(gè)數(shù)據(jù)，一次磁盤 IO 只能取出來一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)加載到內(nèi)存里，如查詢 id=7 這個(gè)數(shù)據(jù)我們就要進(jìn)行磁盤 IO 三次，這很消耗時(shí)間。所以我們?cè)O(shè)計(jì)數(shù)據(jù)庫索引時(shí)需要首先考慮怎么盡可能減少磁盤 IO 的次數(shù)。因此 不能直接用于實(shí)現(xiàn) Mysql 底層索引.。

B-Tree 索引原理

磁盤 IO 特點(diǎn)：從磁盤讀取1B 數(shù)據(jù)和 1KB 數(shù)據(jù)所消耗的時(shí)間是基本一樣的(空間局部性與時(shí)間局部性決定)，根據(jù)這個(gè)思路，可以在一個(gè)樹節(jié)點(diǎn)上盡可能多地存儲(chǔ)數(shù)據(jù)，一次磁盤 IO 就盡可能多的加載數(shù)據(jù)到內(nèi)存，影響數(shù)據(jù)查詢時(shí)間的是樹的高度，高度越高，比較的次數(shù)越多，盡量把樹的高度降低。這就是 B 樹的的設(shè)計(jì)原理了
B-Tree特點(diǎn):

1. 葉節(jié)點(diǎn)具有相同的深度。
2. 節(jié)點(diǎn)中的元素從左向右遞增排序
3. 所有的元素不重復(fù)

B-Tree演化過程：
下圖所示B-Tree樹，每個(gè)節(jié)點(diǎn)限制最多存儲(chǔ)兩個(gè) key，一個(gè)節(jié)點(diǎn)如果超過兩個(gè) key 就會(huì)自動(dòng)分裂。比如下面這個(gè)存儲(chǔ)了 7 個(gè)數(shù)據(jù) B 樹，只需要查詢兩個(gè)節(jié)點(diǎn)就可以知道 id=7 這數(shù)據(jù)的具體位置，也就是兩次磁盤 IO 就可以查詢到指定數(shù)據(jù)，優(yōu)于 AVL 樹。

B-tree.jpg

磁盤有預(yù)讀機(jī)制，每次讀的時(shí)候都是加載一個(gè)磁盤頁到內(nèi)存里面，就是一次磁盤I/o讀取只能讀一個(gè)磁盤頁大?。?kb）的數(shù)據(jù)到內(nèi)存中，也就是8kb的數(shù)據(jù)，要磁盤i/o的2次操作。就是因?yàn)榇疟P預(yù)讀機(jī)制，樹的節(jié)點(diǎn)不能隨便我們?cè)O(shè)置，樹節(jié)點(diǎn)的數(shù)據(jù)量正好是一個(gè)磁盤頁的大小，這樣效率最高，一次IO讀取一個(gè)樹節(jié)點(diǎn)。這個(gè)直接反映到樹的結(jié)構(gòu)就是，每個(gè)節(jié)點(diǎn)能存儲(chǔ)的 key 可以適當(dāng)增加。當(dāng)我們把單個(gè)節(jié)點(diǎn)限制的 key 個(gè)數(shù)設(shè)置為 6 之后，一個(gè)存儲(chǔ)了 7 個(gè)數(shù)據(jù)的 B 樹，查詢 id=7 這個(gè)數(shù)據(jù)所要進(jìn)行的磁盤 IO 為 2 次。如下圖所示：

MySQL頁的大小為16kb，操作系統(tǒng)文件管理系統(tǒng)一次IO讀取的數(shù)據(jù)大小同樣為1頁（4kb）相當(dāng)于8個(gè)扇區(qū)（512bytes ）

B-tree-search.jpg

一個(gè)存儲(chǔ)了 16 個(gè)數(shù)據(jù)的 B 樹，查詢 id=7 這個(gè)數(shù)據(jù)所要進(jìn)行的磁盤 IO 為 2 次。相對(duì)于 AVL 樹而言磁盤 IO 次數(shù)降低為一半,如下圖所示:

B-tree-16.jpg

索引葉節(jié)點(diǎn)數(shù)據(jù)之間的存儲(chǔ)關(guān)系，如下圖所示:

b-tree-data.jpg

假如我們要查找id=28的用戶信息，那么我們?cè)谏蠄DB樹中查找的流程如下：

1. 先找到根節(jié)點(diǎn)也就是頁1，判斷28在鍵值17和35之間，我們那么我們根據(jù)頁1中的指針p2找到頁3。
2. 將28和頁3中的鍵值相比較，28在26和30之間，我們根據(jù)頁3中的指針p2找到頁8。
3. 將28和頁8中的鍵值相比較，發(fā)現(xiàn)有匹配的鍵值28，鍵值28對(duì)應(yīng)的用戶信息為(28,bv)

總結(jié)來說，B 樹用作數(shù)據(jù)庫索引有以下優(yōu)點(diǎn)：

1. 優(yōu)秀檢索速度
2. 盡可能少的磁盤 IO，加快了檢索速度；
3. 可以支持范圍查找。

B+Treee

有了B樹知識(shí)鋪墊，一個(gè)樹節(jié)點(diǎn)我們應(yīng)該盡可能的包含更多的子節(jié)點(diǎn)，但又不能超過一個(gè)磁盤頁（16kb）的大小。發(fā)現(xiàn)B樹的節(jié)點(diǎn)中還包含了一些關(guān)鍵字信息data，這個(gè)data也占據(jù)著一定的數(shù)據(jù)量，r如果把data去掉，這樣就又能多加幾個(gè)子節(jié)點(diǎn)了。這也就是B+樹的核心思想。

查看頁節(jié)點(diǎn)大小

注： show GLOBAL STATUS like 'Innodb_page_size';

mysql 一般將根節(jié)點(diǎn) 限制的大小是 16kb，根節(jié)點(diǎn)的大小存儲(chǔ)大約 1000多個(gè)，底部含有data的為葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)全部放滿 大約為2000萬個(gè)左右。16*1024/(8+6)=1170 主鍵存儲(chǔ) bigint 為8字節(jié)空白部分為索引位置6字節(jié) 16kb為總的根節(jié)點(diǎn)大小

B+Tree特點(diǎn)：

1. 非葉子節(jié)點(diǎn)不存儲(chǔ)data,只存儲(chǔ)索引(冗余),可以放更多的索引
2. 葉子節(jié)點(diǎn)包含所有索引字段
3. 葉子節(jié)點(diǎn)用雙向指針相連，提高區(qū)間訪問性

B+樹是通過二叉樹，平衡二叉樹，B樹和索引順序訪問演化而來,是對(duì)B樹的進(jìn)一步優(yōu)化。

B+Tree結(jié)構(gòu)圖:

B+tree-data.jpg

根據(jù)上圖我們來看下B+樹和B樹有什么不同:

1. B+樹非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)的，僅存儲(chǔ)鍵值(索引地址)，而B樹節(jié)點(diǎn)中不僅存儲(chǔ)鍵值，也會(huì)存儲(chǔ)數(shù)據(jù)。B+樹之所以這么做是因?yàn)樵跀?shù)據(jù)庫中頁的大小是固定的，innodb中頁的默認(rèn)大小是16KB。如果不存儲(chǔ)數(shù)據(jù)，那么就會(huì)存儲(chǔ)更多的鍵值，相應(yīng)的樹的階數(shù)（節(jié)點(diǎn)的子節(jié)點(diǎn)樹）就會(huì)更大，樹就會(huì)更矮更胖，如此一來我們查找數(shù)據(jù)進(jìn)行磁盤的IO次數(shù)會(huì)再次減少，數(shù)據(jù)查詢的效率也會(huì)更快 。

2. B+樹索引的所有數(shù)據(jù)均存儲(chǔ)在葉子節(jié)點(diǎn)，且數(shù)據(jù)是按照順序排列的。B+樹使得范圍查找，排序查找，分組查找以及去重查找變得簡(jiǎn)單高效

3. B+樹各個(gè)頁之間是通過雙向鏈表連接，葉子節(jié)點(diǎn)中的數(shù)據(jù)是通過單向鏈表連接的。我們通過雙向鏈表和單向鏈表連接的方式可以找到表中所有的數(shù)據(jù)。

MySql中 B+Tree詳解

在 mysql分別創(chuàng)建 以myisam 和 Innodb 作為存儲(chǔ)引擎的數(shù)據(jù)表。
Innodb 創(chuàng)建表后生成的文件有：

1. frm:創(chuàng)建表的語句
2. idb:表里面的數(shù)據(jù)+索引文件

Myisam 創(chuàng)建表后生成的文件有：

1. frm:創(chuàng)建表的語句
2. MYD:表里面的數(shù)據(jù)文件（myisam data）
3. MYI:表里面的索引文件（myisam index）

Myisam不支持事務(wù)原因索引與數(shù)據(jù)分開存儲(chǔ)，兩個(gè)文件無法做到一致性

1. MyISAM 引擎的底層實(shí)現(xiàn)（非聚集索引方式）

MyISAM 是非聚集索引方式，即數(shù)據(jù)和索引落在不同的兩個(gè)文件上。B+樹索引的葉子節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)，而是存儲(chǔ)數(shù)據(jù)的文件地址，MyISAM 在建表時(shí)以主鍵作為 KEY 來建立主索引 B+樹，樹的葉子節(jié)點(diǎn)存的是對(duì)應(yīng)數(shù)據(jù)的物理地址。拿到這個(gè)物理地址后，就可以到 MyISAM 數(shù)據(jù)文件中直接定位到具體的數(shù)據(jù)記錄了。下圖所示：

myisam-b+tree.jpg

Myisam檢索數(shù)據(jù)過程中有 "回表操作"

2. Innodb 引擎的底層實(shí)現(xiàn)（聚集索引方式）

InnoDB 是聚集索引方式，因此數(shù)據(jù)和索引都存儲(chǔ)在同一個(gè)文件里。首先 InnoDB 會(huì)根據(jù)主鍵 ID 作為 KEY 建立索引 B+樹，如左下圖所示，而 B+樹的葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵 ID 對(duì)應(yīng)的數(shù)據(jù)，比如在執(zhí)行 select * from user_info where id=15 這個(gè)語句時(shí)，InnoDB 就會(huì)查詢這顆主鍵 ID 索引 B+樹，找到對(duì)應(yīng)的 user_name='Bob'。
這是建表的時(shí)候 InnoDB 就會(huì)自動(dòng)建立好主鍵 ID 索引樹，這也是為什么 Mysql 在建表時(shí)要求必須指定主鍵的原因。當(dāng)我們?yōu)楸砝锬硞€(gè)字段加索引時(shí) InnoDB 會(huì)怎么建立索引樹呢？比如我們要給 user_name 這個(gè)字段加索引，那么 InnoDB 就會(huì)建立 user_name 索引 B+樹，節(jié)點(diǎn)里存的是 user_name 這個(gè) KEY，葉子節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)的是主鍵 KEY。注意，葉子存儲(chǔ)的是主鍵 KEY！拿到主鍵 KEY 后，InnoDB 才會(huì)去主鍵索引樹里根據(jù)剛在 user_name 索引樹找到的主鍵 KEY 查找到對(duì)應(yīng)的數(shù)據(jù)。

Inodb存儲(chǔ)引擎特點(diǎn):

1. 表本身是按B+Tree組織的一個(gè)索引結(jié)構(gòu)文件
2. 葉子節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄
3. 非主鍵索引結(jié)構(gòu)葉子節(jié)點(diǎn)存儲(chǔ)的是主鍵的值，使其保持一致性和節(jié)省空間

B+Tree+Inodb.jpg

Inodb查詢等于的查詢 引擎會(huì)自動(dòng)使用哈希索引進(jìn)行查詢,存儲(chǔ)引擎會(huì)監(jiān)控對(duì)表上索引的查找，如果觀察到建立哈希索引可以帶來速度的提升，則建立哈希索引，所以稱之為自適應(yīng)哈希索引。自適應(yīng)哈希索引通過緩沖池的B+樹構(gòu)造而來，因此建立的速度很快。而且不需要將整個(gè)表都建哈希索引，InnoDB存儲(chǔ)引擎會(huì)自動(dòng)根據(jù)訪問的頻率和模式來為某些頁建立哈希索引。

3. 為什么 InnoDB 只在主鍵索引樹的葉子節(jié)點(diǎn)存儲(chǔ)了具體數(shù)據(jù) ?

為節(jié)省存儲(chǔ)空間，一個(gè)表里可能有很多個(gè)索引，InnoDB 都會(huì)給每個(gè)加了索引的字段生成索引樹，如果每個(gè)字段的索引樹都存儲(chǔ)了具體數(shù)據(jù)，那么這個(gè)表的索引數(shù)據(jù)文件就變得非常巨大（數(shù)據(jù)極度冗余了）。

4. 為什么Inodb表必須有主鍵，且推薦使用整型自增主鍵?

Inodb 會(huì)自動(dòng)選擇不重復(fù)的列作為索引列，組織整張表的數(shù)據(jù)，如果找不到 就會(huì)建隱藏列，所以Inodb一般會(huì)建主鍵,整型的數(shù)據(jù)比較大小速度快，整型存儲(chǔ)占用空間小，主鍵如果不自增，葉子節(jié)點(diǎn) 會(huì)頻繁的發(fā)生分裂，或者平衡變化，會(huì)降低插入的效率，所以主鍵選擇自增整型

數(shù)據(jù)表的字段加索引原則：

1. 較頻繁的作為查詢條件的字段應(yīng)該創(chuàng)建索引；

2. 唯一性太差的字段不適合單獨(dú)創(chuàng)建索引，即使該字段頻繁作為查詢條件；

3. 更新非常頻繁的字段不適合創(chuàng)建索引。

4. 聯(lián)合索引底層數(shù)據(jù)結(jié)構(gòu)

聯(lián)合索引.jpg

聯(lián)合索引的數(shù)據(jù)結(jié)構(gòu) 也是字典排序法則，將第一個(gè) 第二個(gè)進(jìn)行排序，B+之所以高效是借助 葉子節(jié)點(diǎn)從左到右的排序，如果跳過 第一個(gè)字段，則第二三字段 在葉子節(jié)點(diǎn)中的排序 不是按順序排序，則整個(gè)數(shù)據(jù)不一定是順序遞增的結(jié)構(gòu)，就是說聯(lián)合索引使用時(shí)遵循"最左前綴原則"

非主鍵索引存儲(chǔ)的是主鍵索引位置，會(huì)掃描兩棵樹 （主鍵索引, 非主鍵索引）