索引是什么

索引是什么

索引圖解

維基百科對數(shù)據(jù)庫索引的定義:
數(shù)據(jù)庫索引,是數(shù)據(jù)庫管理系統(tǒng)(DBMS)中一個排序的數(shù)據(jù)結構,以協(xié)助快速查詢,更新數(shù)據(jù)庫表中數(shù)據(jù)

怎么理解這個定義呢?

首先數(shù)據(jù)是以文件的形式存放在磁盤上面的,每一行數(shù)據(jù)都有它的磁盤地址.如果沒有索引的話,要從500萬行數(shù)據(jù)里面檢索一條數(shù)據(jù),只能依次遍歷這張表的全部數(shù)據(jù),直到找到這條數(shù)據(jù)
但是有了索引之后,只需要在索引里面去檢索這條數(shù)據(jù)就行了,因為它是一種特殊的專門用來快速檢索的數(shù)據(jù)結構,我們找到數(shù)據(jù)存放的磁盤地址以后,就可以拿到數(shù)據(jù)了
就像我們從一本500頁的書里面去找特定的一小節(jié)的內容,肯定不可能從第一頁開始翻.那么這本書有專門的目錄,它可能只有幾頁的內容,它是按頁碼來組織的,可以根據(jù)拼音或者偏旁部首來查找,只要確定內容對應的頁碼,就能很快地找到我們想要的內容

索引類型

怎么創(chuàng)建一個索引?

第一個是索引的名稱,第二個是索引的列,比如我們是要對 id 創(chuàng)建索引還是對 name 創(chuàng)建索引.后面兩個很重要,一個叫索引類型
在 InnoDB 里面,索引類型有三種,普通索引,唯一索引(主鍵索引是特殊的唯一索引),全文索引

• 普通(Normal):也叫非唯一索引,是最普通的索引,沒有任何的限制
• 唯一(Unique):唯一索引要求鍵值不能重復.另外需要注意的是,主鍵索引是一種特殊的唯一索引,它還多了一個限制條件,要求鍵值不能為空.主鍵索引用 primaykey 創(chuàng)建
• 全文(Fulltext):針對比較大的數(shù)據(jù),比如我們存放的是消息內容,有幾 KB 的數(shù)據(jù)的這種情況,如果要解決 like 查詢效率低的問題,可以創(chuàng)建全文索引.只有文本類型的字段才可以創(chuàng)建全文索引,比如 char,varchar,text

create table m3(
    name varchar(50),
    fulltext index(name)
);

全文索引的使用:

select * from fulltext_test where match(content)against('咕泡學院' IN NATURAL LANGUAGE MODE);

MyISAM 和 InnoDB 支持全文索引
這個是索引的三種類型:普通,唯一,全文
我們說索引是一種數(shù)據(jù)結構,那么它到底應該選擇一種什么數(shù)據(jù)結構,才能實現(xiàn)數(shù)據(jù)的高效檢索呢?

索引存儲模型推演

二分查找

雙十一過去之后,你女朋友跟你玩了一個猜數(shù)字的游戲
猜猜我昨天買了多少錢,給你五次機會
10000?低了.30000?高了.接下來你會猜多少?
20000.為什么你不猜11000,也不猜29000呢?

其實這個就是二分查找的一種思想,也叫折半查找,每一次,我們都把候選數(shù)據(jù)縮小了一半.如果數(shù)據(jù)已經排過序的話,這種方式效率比較高
所以第一個,我們可以考慮用有序數(shù)組作為索引的數(shù)據(jù)結構
有序數(shù)組的等值查詢和比較查詢效率非常高,但是更新數(shù)據(jù)的時候會出現(xiàn)一個問題,可能要挪動大量的數(shù)據(jù)(改變 index),所以只適合存儲靜態(tài)的數(shù)據(jù).為了支持頻繁的修改,比如插入數(shù)據(jù),我們需要采用鏈表.鏈表的話,如果是單鏈表,它的查找效率還是不夠高
所以,有沒有可以使用二分查找的鏈表呢?
為了解決這個問題,BST(BinarySearchTree)也就是我們所說的二叉查找樹誕生了

二叉查找樹(BST Binary Search Tree)

二叉查找樹的特點是什么?
左子樹所有的節(jié)點都小于父節(jié)點,右子樹所有的節(jié)點都大于父節(jié)點.投影到平面以后,就是一個有序的線性表

二叉查找樹既能夠實現(xiàn)快速查找,又能夠實現(xiàn)快速插入
但是二叉查找樹有一個問題:就是它的查找耗時是和這棵樹的深度相關的,在最壞的情況下時間復雜度會退化成 O(n)

什么情況是最壞的情況呢?
我們打開這樣一個網(wǎng)站來看一下,這里面有各種各樣的數(shù)據(jù)結構的動態(tài)演示,包括 BST 二叉查找樹:
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
還是剛才的這一批數(shù)字,如果我們插入的數(shù)據(jù)剛好是有序的,2,6,11,13,17,22

這個時候我們的二叉查找樹變成了什么樣了呢?
它會變成鏈表(我們把這種樹叫做“斜樹”),這種情況下不能達到加快檢索速度的目的,和順序查找效率是沒有區(qū)別的

造成它傾斜的原因是什么呢?因為左右子樹深度差太大,這棵樹的左子樹根本沒有節(jié)點——也就是它不夠平衡.所以,我們有沒有左右子樹深度相差不是那么大,更加平衡的樹呢?
這個就是平衡二叉樹,叫做 Balancedbinarysearchtrees,或者 AVL 樹(AVL 是發(fā)明這個數(shù)據(jù)結構的人的名字)

平衡二叉樹(AVL Tree)(左旋,右旋)

AVLTrees(Balancedbinarysearchtrees)平衡二叉樹的定義:左右子樹深度差絕對值不能超過 1
是什么意思呢?比如左子樹的深度是2,右子樹的深度只能是1或者3.這個時候我們再按順序插入1,2,3,4,5,6,一定是這樣,不會變成一棵“斜樹”

那它的平衡是怎么做到的呢?怎么保證左右子樹的深度差不能超過1呢?
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

插入1,2,3
我們注意看:當我們插入了1,2之后,如果按照二叉查找樹的定義,3肯定是要在2的右邊的,這個時候根節(jié)點1的右節(jié)點深度會變成2,但是左節(jié)點的深度是0,因為它沒有子節(jié)點,所以就會違反平衡二叉樹的定義
那應該怎么辦呢?因為它是右節(jié)點下面接一個右節(jié)點,右-右型,所以這個時候我們要把2提上去,這個操作叫做左旋

同樣的,如果我們插入7,6,5,這個時候會變成左左型,就會發(fā)生右旋操作,把6提上去

所以為了保持平衡,AVL 樹在插入和更新數(shù)據(jù)的時候執(zhí)行了一系列的計算和調整的操作
平衡的問題我們解決了,那么平衡二叉樹作為索引怎么查詢數(shù)據(jù)?在平衡二叉樹中,一個節(jié)點,它的大小是一個固定的單位,作為索引應該存儲什么
內容?
它應該存儲三塊的內容:

• 第一個是索引的鍵值.比如我們在 id 上面創(chuàng)建了一個索引,我在用 whereid=1 的條件查詢的時候就會找到索引里面的 id 的這個鍵值
• 第二個是數(shù)據(jù)的磁盤地址,因為索引的作用就是去查找數(shù)據(jù)的存放的地址
• 第三個,因為是二叉樹,它必須還要有左子節(jié)點和右子節(jié)點的引用,這樣我們才能找到下一個節(jié)點.比如大于26的時候,走右邊,到下一個樹的節(jié)點,繼續(xù)判斷

如果是這樣存儲數(shù)據(jù)的話,我們來看一下會有什么問題
在分析用 AVL 樹存儲索引數(shù)據(jù)之前,我們先來學習一下 InnoDB 的邏輯存儲結構

InnoDB 邏輯存儲結構

https://dev.mysql.com/doc/refman/5.7/en/innodb-disk-management.html
https://dev.mysql.com/doc/refman/5.7/en/innodb-file-space.html

MySQL 的存儲結構分為 5 級:表空間,段,簇,頁,行

表空間 Table Space

上節(jié)課講磁盤結構的時候講過了,表空間可以看做是 InnoDB 存儲引擎邏輯結構的最高層,所有的數(shù)據(jù)都存放在表空間中.分為:系統(tǒng)表空間,獨占表空間,通用表空間,臨時表空間,Undo 表空間

段 Segment

表空間是由各個段組成的,常見的段有數(shù)據(jù)段,索引段,回滾段等,段是一個邏輯的概念.一個 ibd 文件(獨立表空間文件)里面會由很多個段組成
創(chuàng)建一個索引會創(chuàng)建兩個段,一個是索引段:leafnodesegment,一個是數(shù)據(jù)段:non-leafnodesegment.索引段管理非葉子節(jié)點的數(shù)據(jù).數(shù)據(jù)段管理葉子節(jié)點的數(shù)據(jù).也就是說,一個表的段數(shù),就是索引的個數(shù)乘以 2

簇 Extent

一個段(Segment)又由很多的簇(也可以叫區(qū))組成,每個區(qū)的大小是 1MB(64 個連續(xù)的頁)
每一個段至少會有一個簇,一個段所管理的空間大小是無限的,可以一直擴展下去,但是擴展的最小單位就是簇

頁 Page

為了高效管理物理空間,對簇進一步細分,就得到了頁.簇是由連續(xù)的頁(Page)組成的空間,一個簇中有 64 個連續(xù)的頁.(1MB／16KB=64).這些頁面在物理上和邏輯上都是連續(xù)的
跟大多數(shù)數(shù)據(jù)庫一樣,InnoDB 也有頁的概念(也可以稱為塊),每個頁默認 16KB.頁是 InnoDB 存儲引擎磁盤管理的最小單位,通過 innodb_page_size 設置
一個表空間最多擁有 2^32 個頁,默認情況下一個頁的大小為 16KB,也就是說一個表空間最多存儲 64TB 的數(shù)據(jù)

注意,文件系統(tǒng)中,也有頁的概念
操作系統(tǒng)和內存打交道,最小的單位是頁 Page.文件系統(tǒng)的內存頁通常是 4K

SHOW VARIABLES LIKE 'innodb_page_size';

假設一行數(shù)據(jù)大小是 1K,那么一個數(shù)據(jù)頁可以放 16 行這樣的數(shù)據(jù)
舉例:一個頁放3行數(shù)據(jù)

往表中插入數(shù)據(jù)時,如果一個頁面已經寫完,產生一個新的葉頁面.如果一個簇的所有的頁面都被用完,會從當前頁面所在段新分配一個簇

如果數(shù)據(jù)不是連續(xù)的,往已經寫滿的頁中插入數(shù)據(jù),會導致葉頁面分裂:

行 Row

InnoDB 存儲引擎是面向行的(row-oriented),也就是說數(shù)據(jù)的存放按行進行存放
https://dev.mysql.com/doc/refman/5.7/en/innodb-row-format.html

Antelope??nt?l??p是 InnoDB 內置的文件格式,有兩種行格式

• REDUNDANT[r??d?nd?nt]RowFormat
• COMPACTRowFormat(5.6 默認)

Barracuda?b?r??kju?d?是 InnoDBPlugin 支持的文件格式,新增了兩種行格式:

• DYNAMICRowFormat(5.7 默認)
• COMPRESSEDRowFormat

innodb_file_format 在配置文件中指定；row_format 則在創(chuàng)建數(shù)據(jù)表時指定

show variables like "%innodb_file_format%";
SET GLOBAL innodb_file_format=Barracuda;

在創(chuàng)建表的時候可以指定行格式

CREATE TABLE tf1 (c1 INT PRIMARY KEY)ROW_FORMAT = COMPRESSED KEY_BLOCK_SIZE = 8;

查看行格式:

SHOW TABLE STATUS LIKE 'student' \G;

這一塊的內容主要是讓大家了解頁 page 的概念
下面我們繼續(xù)看一下,用 AVL 樹存儲索引數(shù)據(jù),會有什么樣的問題

AVL 樹用于存儲索引數(shù)據(jù)

首先,索引的數(shù)據(jù),是放在硬盤上的.查看數(shù)據(jù)和索引的大小:

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB')AS data_len, CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB')as index_len from information_schema.TABLES where table_schema='gupao' and table_name='user_innodb';

當我們用樹的結構來存儲索引的時候,訪問一個節(jié)點就要跟磁盤之間發(fā)生一次 IO.InnoDB 操作磁盤的最小的單位是一頁(或者叫一個磁盤塊),大小是 16K(16384 字節(jié))
那么,一個樹的節(jié)點就是 16K 的大小
如果我們一個節(jié)點只存一個鍵值+數(shù)據(jù)+引用,例如整形的字段,可能只用了十幾個或者幾十個字節(jié),它遠遠達不到 16K 的容量,所以訪問一個樹節(jié)點,進行一次 IO 的時候,浪費了大量的空間
所以如果每個節(jié)點存儲的數(shù)據(jù)太少,從索引中找到我們需要的數(shù)據(jù),就要訪問更多的節(jié)點,意味著跟磁盤交互次數(shù)就會過多
如果是機械硬盤時代,每次從磁盤讀取數(shù)據(jù)需要 10ms 左右的尋址時間,交互次數(shù)越多,消耗的時間就越多

比如上面這張圖,我們一張表里面有 6 條數(shù)據(jù),當我們查詢 id=37 的時候,要查詢兩個子節(jié)點,就需要跟磁盤交互 3 次,如果我們有幾百萬的數(shù)據(jù)呢?這個時間更加難以估計

所以我們的解決方案是什么呢?

• 第一個就是讓每個節(jié)點存儲更多的數(shù)據(jù)
• 第二個,節(jié)點上的關鍵字的數(shù)量越多,我們的指針數(shù)也越多,也就是意味著可以有更多的分叉(我們把它叫做“路數(shù)”)

因為分叉數(shù)越多,樹的深度就會減少(根節(jié)點是0)
這樣,我們的樹是不是從原來的高瘦高瘦的樣子,變成了矮胖矮胖的樣子?
這個時候,我們的樹就不再是二叉了,而是多叉,或者叫做多路

多路平衡查找樹(B Tree)(分裂,合并)

BalancedTree
這個就是我們的多路平衡查找樹,叫做 BTree(B 代表平衡)
跟 AVL 樹一樣,B 樹在枝節(jié)點和葉子節(jié)點存儲鍵值,數(shù)據(jù)地址,節(jié)點引用
它有一個特點:分叉數(shù)(路數(shù))永遠比關鍵字數(shù)多1.比如我們畫的這棵樹,每個節(jié)點存儲兩個關鍵字,那么就會有三個指針指向三個子節(jié)點

BTree 的查找規(guī)則是什么樣的呢?
比如我們要在這張表里面查找15
因為15小于17,走左邊
因為15大于12,走右邊
在磁盤塊 7 里面就找到了 15,只用了 3 次 IO

這個是不是比 AVL 樹效率更高呢?
那 BTree 又是怎么實現(xiàn)一個節(jié)點存儲多個關鍵字,還保持平衡的呢?跟 AVL 樹有什么區(qū)別?
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

比如 MaxDegree(路數(shù))是 3 的時候,我們插入數(shù)據(jù) 1,2,3,在插入 3 的時候,本來應該在第一個磁盤塊,但是如果一個節(jié)點有三個關鍵字的時候,意味著有 4 個指針,子節(jié)點會變成 4 路,所以這個時候必須進行分裂.把中間的數(shù)據(jù) 2 提上去,把 1 和 3 變成 2 的子節(jié)點
如果刪除節(jié)點,會有相反的合并的操作
注意這里是分裂和合并,跟 AVL 樹的左旋和右旋是不一樣的
我們繼續(xù)插入 4 和 5,BTree 又會出現(xiàn)分裂和合并的操作

從這個里面我們也能看到,在更新索引的時候會有大量的索引的結構的調整,所以解釋了為什么我們不要在頻繁更新的列上建索引,或者為什么不要更新主鍵
節(jié)點的分裂和合并,其實就是 InnoDB 頁的分裂和合并

B+樹(加強版多路平衡查找樹)

BTree 的效率已經很高了,為什么 MySQL 還要對 BTree 進行改良,最終使用了 B+Tree 呢?
總體上來說,這個 B 樹的改良版本解決的問題比 BTree 更全面
我們來看一下 InnoDB 里面的 B+樹的存儲結構:

MySQL 中的 B+Tree 有幾個特點:

• 它的關鍵字的數(shù)量是跟路數(shù)相等的
• B+Tree 的根節(jié)點和枝節(jié)點中都不會存儲數(shù)據(jù),只有葉子節(jié)點才存儲數(shù)據(jù).搜索到關鍵字不會直接返回,會到最后一層的葉子節(jié)點.比如我們搜索 id=28,雖然在第一層直接命中了,但是全部的數(shù)據(jù)在葉子節(jié)點上面,所以我還要繼續(xù)往下搜索,一直到葉子節(jié)點

舉個例子:假設一條記錄是 1K,一個葉子節(jié)點(一頁)可以存儲 16 條記錄.非葉子節(jié)點可以存儲多少個指針?
假設索引字段是 bigint 類型,長度為 8 字節(jié).指針大小在 InnoDB 源碼中設置為 6 字節(jié),這樣一共 14 字節(jié).非葉子節(jié)點(一頁)可以存儲 16384/14=1170 個這樣的單元(鍵值+指針),代表有 1170 個指針
樹深度為 2 的時候,有 1170^2 個葉子節(jié)點,可以存儲的數(shù)據(jù)為 1170117016=21902400

在查找數(shù)據(jù)時一次頁的查找代表一次 IO,也就是說,一張 2000 萬左右的表,查詢數(shù)據(jù)最多需要訪問 3 次磁盤
所以在 InnoDB 中 B+樹深度一般為 1-3 層,它就能滿足千萬級的數(shù)據(jù)存儲

• B+Tree 的每個葉子節(jié)點增加了一個指向相鄰葉子節(jié)點的指針,它的最后一個數(shù)據(jù)會指向下一個葉子節(jié)點的第一個數(shù)據(jù),形成了一個有序鏈表的結構
• 它是根據(jù)左閉右開的區(qū)間[)來檢索數(shù)據(jù)

我們來看一下 B+Tree 的數(shù)據(jù)搜尋過程:

• 比如我們要查找 28,在根節(jié)點就找到了鍵值,但是因為它不是頁子節(jié)點,所以會繼續(xù)往下搜尋,28 是[28,66)的左閉右開的區(qū)間的臨界值,所以會走中間的子節(jié)點,然后繼續(xù)搜索,它又是[28,34)的左閉右開的區(qū)間的臨界值,所以會走左邊的子節(jié)點,最后在葉子節(jié)點上找到了需要的數(shù)據(jù)
• 第二個,如果是范圍查詢,比如要查詢從22到60的數(shù)據(jù),當找到22之后,只需要順著節(jié)點和指針順序遍歷就可以一次性訪問到所有的數(shù)據(jù)節(jié)點,這樣就極大地提高了區(qū)間查詢效率(不需要返回上層父節(jié)點重復遍歷查找)

總結一下,InnoDB 中的 B+Tree 的特點:

• 它是 BTree 的變種,BTree 能解決的問題,它都能解決.BTree 解決的兩大問題是什么?(每個節(jié)點存儲更多關鍵字；路數(shù)更多)
• 掃庫,掃表能力更強(如果我們要對表進行全表掃描,只需要遍歷葉子節(jié)點就可以了,不需要遍歷整棵 B+Tree 拿到所有的數(shù)據(jù))
• B+Tree 的磁盤讀寫能力相對于 BTree 來說更強(根節(jié)點和枝節(jié)點不保存數(shù)據(jù)區(qū),所以一個節(jié)點可以保存更多的關鍵字,一次磁盤加載的關鍵字更多)
• 排序能力更強(因為葉子節(jié)點上有下一個數(shù)據(jù)區(qū)的指針,數(shù)據(jù)形成了鏈表)
• 效率更加穩(wěn)定(B+Tree 永遠是在葉子節(jié)點拿到數(shù)據(jù),所以 IO 次數(shù)是穩(wěn)定的)

為什么不用紅黑樹?

紅黑樹也是 BST 樹,但是不是嚴格平衡的
必須滿足5個約束:

• 節(jié)點分為紅色或者黑色
• 根節(jié)點必須是黑色的
• 葉子節(jié)點都是黑色的 NULL 節(jié)點
• 紅色節(jié)點的兩個子節(jié)點都是黑色(不允許兩個相鄰的紅色節(jié)點)
• 從任意節(jié)點出發(fā),到其每個葉子節(jié)點的路徑中包含相同數(shù)量的黑色節(jié)點,插入:60,56,68,45,64,58,72,43,49

基于以上規(guī)則,可以推導出:
從根節(jié)點到葉子節(jié)點的最長路徑(紅黑相間的路徑)不大于最短路徑(全部是黑色節(jié)點)的2倍
為什么不用紅黑樹?1,只有兩路；2,不夠平衡
紅黑樹一般只放在內存里面用.例如 Java 的 TreeMap

索引方式:真的是用的 B+Tree 嗎?

在 Navicat 的工具中,創(chuàng)建索引,索引方式有兩種,Hash 和 BTree
HASH:以 KV 的形式檢索數(shù)據(jù),也就是說,它會根據(jù)索引字段生成哈希碼和指針,指針指向數(shù)據(jù)

哈希索引有什么特點呢?

• 第一個,它的時間復雜度是 O(1),查詢速度比較快.因為哈希索引里面的數(shù)據(jù)不是按順序存儲的,所以不能用于排序
• 第二個,我們在查詢數(shù)據(jù)的時候要根據(jù)鍵值計算哈希碼,所以它只能支持等值查詢(=IN),不支持范圍查詢(><>=<=betweenand)
• 另外一個就是如果字段重復值很多的時候,會出現(xiàn)大量的哈希沖突(采用拉鏈法解決),效率會降低

問題:InnoDB 可以在客戶端創(chuàng)建一個索引,使用哈希索引嗎?
https://dev.mysql.com/doc/refman/5.7/en/innodb-introduction.html
InnoDButilizeshashindexesinternallyforitsAdaptiveHashIndexfeature

直接翻譯過來就是:InnoDB 內部使用哈希索引來實現(xiàn)自適應哈希索引特性
這句話的意思是 InnoDB 只支持顯式創(chuàng)建 B+Tree 索引,對于一些熱點數(shù)據(jù)頁,InnoDB 會自動建立自適應 Hash 索引,也就是在 B+Tree 索引基礎上建立 Hash 索引,這個過程對于客戶端是不可控制的,隱式的
我們在 Navicat 工具里面選擇索引方法是哈希,但是它創(chuàng)建的還是 B+Tree 索引,這個不是我們可以手動控制的
上次課我們說到 bufferpool 里面有一塊區(qū)域是 AdaptiveHashIndex 自適應哈希索引,就是這個

這個開關默認是 ON:

show variables like 'innodb_adaptive_hash_index';

從存儲引擎的運行信息中可以看到:

show engine innodb status\G 24

---------------------- BUFFER POOL AND MEMORY ----------------------
--------------------- INSERT BUFFER AND ADAPTIVE HASH INDEX -------------

因為 BTree 和 B+Tree 的特性,它們廣泛地用在文件系統(tǒng)和數(shù)據(jù)庫中,例如 Windows 的 HPFS 文件系統(tǒng),Oracel,MySQL,SQLServer 數(shù)據(jù)庫

B+Tree 落地形式

MySQL 架構

通過上節(jié)課我們知道,MySQL 是一個支持插件式存儲引擎的數(shù)據(jù)庫.在 MySQL 里面,每個表在創(chuàng)建的時候都可以指定它所使用的存儲引擎
這里我們主要關注一下最常用的兩個存儲引擎,MyISAM 和 InnoDB 的索引的實現(xiàn)

MySQL 數(shù)據(jù)存儲文件

首先,MySQL 的數(shù)據(jù)都是文件的形式存放在磁盤中的,我們可以找到這個數(shù)據(jù)目錄的地址.在 MySQL 中有這么一個參數(shù),我們來看一下:

show VARIABLES LIKE 'datadir';

每個數(shù)據(jù)庫有一個目錄,我們新建了一個叫做 gupao 的數(shù)據(jù)庫,那么這里就有一個 gupao 的文件夾
這個數(shù)據(jù)庫里面我們又建了 5 張表:archive,innodb,memory,myisam,csv
我們進入 gupao 的目錄,發(fā)現(xiàn)這里面有一些跟我們創(chuàng)建的表名對應的文件
在這里我們能看到,每張 InnoDB 的表有兩個文件(.frm 和.ibd),MyISAM 的表有三個文件(.frm,.MYD,.MYI)

有一個是相同的文件,.frm..frm 是 MySQL 里面表結構定義的文件,不管你建表的時候選用任何一個存儲引擎都會生成
我們主要看一下其他兩個文件是怎么實現(xiàn) MySQL 不同的存儲引擎的索引的.

MyISAM

在 MyISAM 里面,另外有兩個文件:

• 一個是.MYD 文件,D 代表 Data,是 MyISAM 的數(shù)據(jù)文件,存放數(shù)據(jù)記錄,比如我們的 user_myisam 表的所有的表數(shù)據(jù)
• 一個是.MYI 文件,I 代表 Index,是 MyISAM 的索引文件,存放索引,比如我們在 id 字段上面創(chuàng)建了一個主鍵索引,那么主鍵索引就是在這個索引文件里面

也就是說,在 MyISAM 里面,索引和數(shù)據(jù)是兩個獨立的文件
那我們怎么根據(jù)索引找到數(shù)據(jù)呢?
MyISAM 的 B+Tree 里面,葉子節(jié)點存儲的是數(shù)據(jù)文件對應的磁盤地址.所以從索引文件.MYI 中找到鍵值后,會到數(shù)據(jù)文件.MYD 中獲取相應的數(shù)據(jù)記錄

這里是主鍵索引,如果是輔助索引,有什么不一樣呢?
在 MyISAM 里面,輔助索引也在這個.MYI 文件里面
輔助索引跟主鍵索引存儲和檢索數(shù)據(jù)的方式是沒有任何區(qū)別的,一樣是在索引文件里面找到磁盤地址,然后到數(shù)據(jù)文件里面獲取數(shù)據(jù)

4.2.2.InnoDBInnoDB 只有一個文件(.ibd 文件),那索引放在哪里呢?在 InnoDB 里面,它是以主鍵為索引來組織數(shù)據(jù)的存儲的,所以索引文件和數(shù)據(jù)文件是同一個文件,都在.ibd 文件里面.在 InnoDB 的主鍵索引的葉子節(jié)點上,它直接存儲了我們的數(shù)據(jù)

什么叫做聚集索引(聚簇索引)?
就是索引鍵值的邏輯順序跟表數(shù)據(jù)行的物理存儲順序是一致的.(比如字典的目錄是按拼音排序的,內容也是按拼音排序的,按拼音排序的這種目錄就叫聚集索引)
在 InnoDB 里面,它組織數(shù)據(jù)的方式叫做叫做(聚集)索引組織表(clusteredindexorganizetable),所以主鍵索引是聚集索引,非主鍵都是非聚集索引
如果 InnoDB 里面主鍵是這樣存儲的,那主鍵之外的索引,比如我們在 name 字段上面建的普通索引,又是怎么存儲和檢索數(shù)據(jù)的呢?

InnoDB 中,主鍵索引和輔助索引是有一個主次之分的
輔助索引存儲的是輔助索引和主鍵值.如果使用輔助索引查詢,會根據(jù)主鍵值在主鍵索引中查詢,最終取得數(shù)據(jù)
比如我們用 name 索引查詢 name='青山',它會在葉子節(jié)點找到主鍵值,也就是 id=1,然后再到主鍵索引的葉子節(jié)點拿到數(shù)據(jù)
為什么在輔助索引里面存儲的是主鍵值而不是主鍵的磁盤地址呢?如果主鍵的數(shù)據(jù)類型比較大,是不是比存地址更消耗空間呢?
我們前面說到 BTree 是怎么實現(xiàn)一個節(jié)點存儲多個關鍵字,還保持平衡的呢?
是因為有分叉和合并的操作,這個時候鍵值的地址會發(fā)生變化,所以在輔助索引里面不能存儲地址

另一個問題,如果一張表沒有主鍵怎么辦?

• 如果我們定義了主鍵(PRIMARYKEY),那么 InnoDB 會選擇主鍵作為聚集索引
• 如果沒有顯式定義主鍵,則 InnoDB 會選擇第一個不包含有 NULL 值的唯一索引作為主鍵索引
• 如果也沒有這樣的唯一索引,則 InnoDB 會選擇內置 6 字節(jié)長的 ROWID 作為隱藏的聚集索引,它會隨著行記錄的寫入而主鍵遞增

select _rowid name from t2;

索引使用原則

我們容易有以一個誤區(qū),就是在經常使用的查詢條件上都建立索引,索引越多越好,那到底是不是這樣呢?

列的離散(sàn)度

第一個叫做列的離散度,我們先來看一下列的離散度的公式:count(distinct(column_name)):count(\*),列的全部不同值和所有數(shù)據(jù)行的比例.數(shù)據(jù)行數(shù)相同的情況下,分子越大,列的離散度就越高

簡單來說,如果列的重復值越多,離散度就越低,重復值越少,離散度就越高
了解了離散度的概念之后,我們再來思考一個問題,我們在 name 上面建立索引和在 gender 上面建立索引有什么區(qū)別
當我們用在 gender 上建立的索引去檢索數(shù)據(jù)的時候,由于重復值太多,需要掃描的行數(shù)就更多.例如,我們現(xiàn)在在 gender 列上面創(chuàng)建一個索引,然后看一下執(zhí)行計劃

ALTER TABLE user_innodb DROP INDEX idx_user_gender;
ALTER TABLE user_innodb ADD INDEX idx_user_gender (gender); -- 耗時比較久
EXPLAIN SELECT * FROM `user_innodb` WHERE gender = 0;

show indexes from user_innodb;

而 name 的離散度更高,比如“青山”的這名字,只需要掃描一行

ALTER TABLE user_innodb DROP INDEX idx_user_name;
ALTER TABLE user_innodb ADD INDEX idx_user_name (name);

EXPLAIN SELECT * FROM `user_innodb` WHERE name = '青山';

查看表上的索引,Cardinality[kɑ:d?'n?l?t?]代表基數(shù),代表預估的不重復的值的數(shù)量.索引的基數(shù)與表總行數(shù)越接近,列的離散度就越高

show indexes from user_innodb;

如果在 B+Tree 里面的重復值太多,MySQL 的優(yōu)化器發(fā)現(xiàn)走索引跟使用全表掃描差不了多少的時候,就算建了索引,也不一定會走索引
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

這個給我們的啟發(fā)是什么?建立索引,要使用離散度(選擇度)更高的字段

聯(lián)合索引最左匹配

前面我們說的都是針對單列創(chuàng)建的索引,但有的時候我們的多條件查詢的時候,也會建立聯(lián)合索引.單列索引可以看成是特殊的聯(lián)合索引
比如我們在 user 表上面,給 name 和 phone 建立了一個聯(lián)合索引

ALTER TABLE user_innodb DROP INDEX comidx_name_phone;
ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);

聯(lián)合索引在 B+Tree 中是復合的數(shù)據(jù)結構,它是按照從左到右的順序來建立搜索樹的(name 在左邊,phone 在右邊)
從這張圖可以看出來,name 是有序的,phone 是無序的.當 name 相等的時候,phone 才是有序的
這個時候我們使用 wherename='青山'andphone='136xx'去查詢數(shù)據(jù)的時候,B+Tree 會優(yōu)先比較 name 來確定下一步應該搜索的方向,往左還是往右.如果 name 相同的時候再比較 phone.但是如果查詢條件沒有 name,就不知道第一步應該查哪個節(jié)點,因為建立搜索樹的時候 name 是第一個比較因子,所以用不到索引

什么時候用到聯(lián)合索引

所以,我們在建立聯(lián)合索引的時候,一定要把最常用的列放在最左邊
比如下面的三條語句,能用到聯(lián)合索引嗎?

• 使用兩個字段,可以用到聯(lián)合索引:

EXPLAIN SELECT * FROM user_innodb WHERE name= '權亮' AND phone = '15204661800'

• 使用左邊的 name 字段,可以用到聯(lián)合索引:

EXPLAIN SELECT * FROM user_innodb WHERE name= '權亮'

• 使用右邊的 phone 字段,無法使用索引,全表掃描:

EXPLAIN SELECT * FROM user_innodb WHERE phone = '15204661800'

如何創(chuàng)建聯(lián)合索引

有一天我們的 DBA 找到我,說我們的項目里面有兩個查詢很慢

SELECT * FROM user_innodb WHERE name= ? AND phone = ?;
SELECT * FROM user_innodb WHERE name= ?;

按照我們的想法,一個查詢創(chuàng)建一個索引,所以我們針對這兩條 SQL 創(chuàng)建了兩個索引,這種做法覺得正確嗎?

CREATE INDEX idx_name on user_innodb(name);
CREATE INDEX idx_name_phone on user_innodb(name,phone);

當我們創(chuàng)建一個聯(lián)合索引的時候,按照最左匹配原則,用左邊的字段 name 去查詢的時候,也能用到索引,所以第一個索引完全沒必要
相當于建立了兩個聯(lián)合索引(name),(name,phone)
如果我們創(chuàng)建三個字段的索引 index(a,b,c),相當于創(chuàng)建三個索引:

• index(a)
• index(a,b)
• index(a,b,c)

用 whereb=?和 whereb=?andc=?和 wherea=?andc=?是不能使用到索引的.不能不用第一個字段,不能中斷
這里就是 MySQL 聯(lián)合索引的最左匹配原則

覆蓋索引

回表:
非主鍵索引,我們先通過索引找到主鍵索引的鍵值,再通過主鍵值查出索引里面沒有的數(shù)據(jù),它比基于主鍵索引的查詢多掃描了一棵索引樹,這個過程就叫回表
例如:select*fromuser_innodbwherename='青山';

在輔助索引里面,不管是單列索引還是聯(lián)合索引,如果 select 的數(shù)據(jù)列只用從索引中就能夠取得,不必從數(shù)據(jù)區(qū)中讀取,這時候使用的索引就叫做覆蓋索引,這樣就避免了回表
我們先來創(chuàng)建一個聯(lián)合索引:

-- 創(chuàng)建聯(lián)合索引
ALTER TABLE user_innodb DROP INDEX comixd_name_phone;
ALTER TABLE user_innodb add INDEX `comixd_name_phone` (`name`,`phone`);

這三個查詢語句都用到了覆蓋索引:

EXPLAIN SELECT name,phone FROM user_innodb WHERE name= '青山' AND phone = ' 13666666666';
EXPLAIN SELECT name FROM user_innodb WHERE name= '青山' AND phone = ' 13666666666';
EXPLAIN SELECT phone FROM user_innodb WHERE name= '青山' AND phone = ' 13666666666';

Extra 里面值為“Usingindex”代表使用了覆蓋索引

select*,用不到覆蓋索引
如果改成只用 wherephone=查詢呢?動手試試?
很明顯,因為覆蓋索引減少了 IO 次數(shù),減少了數(shù)據(jù)的訪問量,可以大大地提升查詢效率

索引條件下推(ICP)

https://dev.mysql.com/doc/refman/5.7/en/index-condition-pushdown-optimization.html
再來看這么一張表,在 last_name 和 first_name 上面創(chuàng)建聯(lián)合索引

drop table employees;
CREATE TABLE `employees` (
    `emp_no` int(11)NOT NULL,
    `birth_date` date NULL,
    `first_name` varchar(14)NOT NULL,
    `last_name` varchar(16)NOT NULL,
    `gender` enum('M','F')NOT NULL,
    `hire_date` date NULL,
    PRIMARY KEY (`emp_no`)
)ENGINE=InnoDB DEFAULT CHARSET=latin1;

alter table employees add index idx_lastname_firstname(last_name,first_name);

INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (1, NULL, '698', 'liu', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (2, NULL, 'd99', 'zheng', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (3, NULL, 'e08', 'huang', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (4, NULL, '59d', 'lu', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (5, NULL, '0dc', 'yu', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (6, NULL, '989', 'wang', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (7, NULL, 'e38', 'wang', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (8, NULL, '0zi', 'wang', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (9, NULL, 'dc9', 'xie', 'F', NULL);
INSERT INTO `employees` (`emp_no`, `birth_date`, `first_name`, `last_name`, `gender`, `hire_date`)VALUES (10, NULL, '5ba', 'zhou', 'F', NULL);

關閉 ICP:

set optimizer_switch='index_condition_pushdown=off';

查看參數(shù):

show variables like 'optimizer_switch';

現(xiàn)在我們要查詢所有姓 wang,并且名字最后一個字是 zi 的員工,比如王胖子,王瘦子.查詢的 SQL:

select * from employees where last_name='wang' and first_name LIKE '%zi' ;

這條 SQL 有兩種執(zhí)行方式:

• 根據(jù)聯(lián)合索引查出所有姓 wang 的二級索引數(shù)據(jù),然后回表,到主鍵索引上查詢全部符合條件的數(shù)據(jù)(3 條數(shù)據(jù)).然后返回給 Server 層,在 Server 層過濾出名字以 zi 結尾的員工
• 根據(jù)聯(lián)合索引查出所有姓 wang 的二級索引數(shù)據(jù)(3 個索引),然后從二級索引中篩選出 first_name 以 zi 結尾的索引(1 個索引),然后再回表,到主鍵索引上查詢全部符合條件的數(shù)據(jù)(1 條數(shù)據(jù)),返回給 Server 層

很明顯,第二種方式到主鍵索引上查詢的數(shù)據(jù)更少
注意,索引的比較是在存儲引擎進行的,數(shù)據(jù)記錄的比較,是在 Server 層進行的.而當 first_name 的條件不能用于索引過濾時,Server 層不會把 first_name 的條件傳遞給存儲引擎,所以讀取了兩條沒有必要的記錄
這時候,如果滿足 last_name='wang'的記錄有 100000 條,就會有 99999 條沒有必要讀取的記錄

執(zhí)行以下 SQL,Usingwhere:

explain select * from employees where last_name='wang' and first_name LIKE '%zi';

UsingWhere 代表從存儲引擎取回的數(shù)據(jù)不全部滿足條件,需要在 Server 層過濾
先用 last_name 條件進行索引范圍掃描,讀取數(shù)據(jù)表記錄,然后進行比較,檢查是否符合 first_nameLIKE'%zi'的條件.此時 3 條中只有 1 條符合條件

開啟 ICP:

set optimizer_switch='index_condition_pushdown=on';

此時的執(zhí)行計劃,Usingindexcondition:

把 first_nameLIKE'%zi'下推給存儲引擎后,只會從數(shù)據(jù)表讀取所需的 1 條記錄

索引條件下推(IndexConditionPushdown),5.6 以后完善的功能.只適用于二級索引.ICP 的目標是減少訪問表的完整行的讀數(shù)量從而減少 I/O 操作

索引的創(chuàng)建與使用

因為索引對于改善查詢性能的作用是巨大的,所以我們的目標是盡量使用索引

索引的創(chuàng)建

• 在用于 where 判斷 order 排序和 join 的(on)字段上創(chuàng)建索引
• 索引的個數(shù)不要過多--浪費空間,更新變慢
• 區(qū)分度低的字段,例如性別,不要建索引--離散度太低,導致掃描行數(shù)過多
• 頻繁更新的值,不要作為主鍵或者索引--頁分裂
• 組合索引把散列性高(區(qū)分度高)的值放在前面
• 創(chuàng)建復合索引,而不是修改單列索引
• 過長的字段,怎么建立索引?
• 為什么不建議用無序的值(例如身份證,UUID)作為索引?

什么時候用不到索引?

• 索引列上使用函數(shù)(replace\SUBSTR\CONCAT\sumcountavg),表達式,計算(+-*/)

explain SELECT * FROM `t2` where id+1 = 4;

• 字符串不加引號,出現(xiàn)隱式轉換

ALTER TABLE user_innodb DROP INDEX comidx_name_phone;
ALTER TABLE user_innodb add INDEX comidx_name_phone (name,phone);

explain SELECT * FROM `user_innodb` where name = 136;
explain SELECT * FROM `user_innodb` where name = '136';

• like 條件中前面帶%,where 條件中 likeabc%,like%2673%,like%888 都用不到索引嗎?為什么?

explain select *from user_innodb where name like 'wang%';
explain select *from user_innodb where name like '%wang';

過濾的開銷太大,所以無法使用索引.這個時候可以用全文索引

• 負向查詢 NOTLIKE 不能:

explain select *from employees where last_name not like 'wang'

!=(<>)和 NOTIN 在某些情況下可以:

explain select *from employees where emp_no not in (1);
explain select *from employees where emp_no <> 1;

注意一個 SQL 語句是否使用索引,跟數(shù)據(jù)庫版本,數(shù)據(jù)量,數(shù)據(jù)選擇度都有關系
其實,用不用索引,最終都是優(yōu)化器說了算.優(yōu)化器是基于什么的優(yōu)化器?
基于 cost 開銷(CostBaseOptimizer),它不是基于規(guī)則(Rule-BasedOptimizer),也不是基于語義.怎么樣開銷小就怎么來

https://docs.oracle.com/cd/B10501_01/server.920/a96533/rbo.htm#38960
https://dev.mysql.com/doc/refman/5.7/en/cost-model.html