背景
我相信大家在數(shù)據(jù)庫優(yōu)化的時候都會說到索引,，我也不例外，大家也基本上能對數(shù)據(jù)結(jié)構(gòu)的優(yōu)化回答個一二三,，以及頁緩存之類的都能扯上幾句,，但是有一次阿里P9的一個面試問我：你能從計算機層面開始說一下一個索引數(shù)據(jù)加載的流程么？（就是想讓我聊IO）
我當(dāng)場就去世了....因為計算機網(wǎng)絡(luò)和操作系統(tǒng)的基礎(chǔ)知識真的是我的盲區(qū),，不過后面我惡補了,，廢話不多說，我們就從計算機加載數(shù)據(jù)聊起,，講一下?lián)Q個角度聊索引,。
正文
MySQL的索引本質(zhì)上是一種數(shù)據(jù)結(jié)構(gòu)
讓我們先來了解一下計算機的數(shù)據(jù)加載。
磁盤IO和預(yù)讀：
先說一下磁盤IO,，磁盤讀取數(shù)據(jù)靠的是機械運動,，每一次讀取數(shù)據(jù)需要尋道、尋點,、拷貝到內(nèi)存三步操作。
尋道時間是磁臂移動到指定磁道所需要的時間,，一般在5ms以下,；
尋點是從磁道中找到數(shù)據(jù)存在的那個點,，平均時間是半圈時間，如果是一個7200轉(zhuǎn)/min的磁盤,，尋點時間平均是600000/7200/2=4.17ms,；
拷貝到內(nèi)存的時間很快，和前面兩個時間比起來可以忽略不計,，所以一次IO的時間平均是在9ms左右,。聽起來很快，但數(shù)據(jù)庫百萬級別的數(shù)據(jù)過一遍就達(dá)到了9000s,，顯然就是災(zāi)難級別的了,。
考慮到磁盤IO是非常高昂的操作，計算機操作系統(tǒng)做了預(yù)讀的優(yōu)化,，當(dāng)一次IO時,，不光把當(dāng)前磁盤地址的數(shù)據(jù)，而是把相鄰的數(shù)據(jù)也都讀取到內(nèi)存緩沖區(qū)內(nèi),，因為當(dāng)計算機訪問一個地址的數(shù)據(jù)的時候,，與其相鄰的數(shù)據(jù)也會很快被訪問到。
每一次IO讀取的數(shù)據(jù)我們稱之為一頁(page),，具體一頁有多大數(shù)據(jù)跟操作系統(tǒng)有關(guān),，一般為4k或8k，也就是我們讀取一頁內(nèi)的數(shù)據(jù)時候,，實際上才發(fā)生了一次IO,。
（突然想到個我剛畢業(yè)被問過的問題，在64位的操作系統(tǒng)中,，Java中的int類型占幾個字節(jié),？最大是多少？為什么,？）
那我們想要優(yōu)化數(shù)據(jù)庫查詢,，就要盡量減少磁盤的IO操作，所以就出現(xiàn)了索引,。
索引是什么,？
MySQL官方對索引的定義為：索引(Index)是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。
MySQL中常用的索引在物理上分兩類,，B-樹索引和哈希索引,。
本次主要講BTree索引。
BTree索引
BTree又叫多路平衡查找樹,，一顆m叉的BTree特性如下：
樹中每個節(jié)點最多包含m個孩子,。
除根節(jié)點與葉子節(jié)點外，每個節(jié)點至少有[ceil(m/2)]個孩子（ceil()為向上取整）,。
若根節(jié)點不是葉子節(jié)點,，則至少有兩個孩子,。
所有的葉子節(jié)點都在同一層。
每個非葉子節(jié)點由n個key與n+1個指針組成,，其中[ceil(m/2)-1] <= n <= m-1 ,。
這是一個3叉（只是舉例，真實會有很多叉）的BTree結(jié)構(gòu)圖,，每一個方框塊我們稱之為一個磁盤塊或者叫做一個block塊,，這是操作系統(tǒng)一次IO往內(nèi)存中讀的內(nèi)容，一個塊對應(yīng)四個扇區(qū),，紫色代表的是磁盤塊中的數(shù)據(jù)key,，黃色代表的是數(shù)據(jù)data，藍(lán)色代表的是指針p,，指向下一個磁盤塊的位置,。
來模擬下查找key為29的data的過程：
1、根據(jù)根結(jié)點指針讀取文件目錄的根磁盤塊1,?！敬疟PIO操作1次】
2、磁盤塊1存儲17,，35和三個指針數(shù)據(jù),。我們發(fā)現(xiàn)17<29<35，因此我們找到指針p2,。
3,、根據(jù)p2指針，我們定位并讀取磁盤塊3,?！敬疟PIO操作2次】
4、磁盤塊3存儲26,，30和三個指針數(shù)據(jù),。我們發(fā)現(xiàn)26<29<30，因此我們找到指針p2,。
5,、根據(jù)p2指針，我們定位并讀取磁盤塊8,?！敬疟PIO操作3次】
6、磁盤塊8中存儲28,，29,。我們找到29，獲取29所對應(yīng)的數(shù)據(jù)data。
由此可見,，BTree索引使每次磁盤I/O取到內(nèi)存的數(shù)據(jù)都發(fā)揮了作用,，從而提高了查詢效率。
但是有沒有什么可優(yōu)化的地方呢,？
我們從圖上可以看到，每個節(jié)點中不僅包含數(shù)據(jù)的key值,，還有data值,。而每一個頁的存儲空間是有限的，如果data數(shù)據(jù)較大時將會導(dǎo)致每個節(jié)點（即一個頁）能存儲的key的數(shù)量很小,，當(dāng)存儲的數(shù)據(jù)量很大時同樣會導(dǎo)致B-Tree的深度較大,，增大查詢時的磁盤I/O次數(shù)，進(jìn)而影響查詢效率,。
B+Tree索引
B+Tree是在B-Tree基礎(chǔ)上的一種優(yōu)化,，使其更適合實現(xiàn)外存儲索引結(jié)構(gòu)。在B+Tree中,，所有數(shù)據(jù)記錄節(jié)點都是按照鍵值大小順序存放在同一層的葉子節(jié)點上,，而非葉子節(jié)點上只存儲key值信息，這樣可以大大加大每個節(jié)點存儲的key值數(shù)量,，降低B+Tree的高度,。
B+Tree相對于B-Tree有幾點不同：
非葉子節(jié)點只存儲鍵值信息， 數(shù)據(jù)記錄都存放在葉子節(jié)點中,， 將上一節(jié)中的B-Tree優(yōu)化,，由于B+Tree的非葉子節(jié)點只存儲鍵值信息，所以B+Tree的高度可以被壓縮到特別的低,。
具體的數(shù)據(jù)如下：
InnoDB存儲引擎中頁的大小為16KB,，一般表的主鍵類型為INT（占用4個字節(jié)）或BIGINT（占用8個字節(jié)），指針類型也一般為4或8個字節(jié),，也就是說一個頁（B+Tree中的一個節(jié)點）中大概存儲16KB/(8B+8B)=1K個鍵值（因為是估值,，為方便計算，這里的K取值為〖10〗^3）,。也就是說一個深度為3的B+Tree索引可以維護(hù)10^3 10^3 10^3 = 10億 條記錄,。（這種計算方式存在誤差，而且沒有計算葉子節(jié)點,，如果計算葉子節(jié)點其實是深度為4了）
我們只需要進(jìn)行三次的IO操作就可以從10億條數(shù)據(jù)中找到我們想要的數(shù)據(jù),，比起最開始的百萬數(shù)據(jù)9000秒不知道好了多少個華萊士了。
而且在B+Tree上通常有兩個頭指針,，一個指向根節(jié)點,，另一個指向關(guān)鍵字最小的葉子節(jié)點，而且所有葉子節(jié)點（即數(shù)據(jù)節(jié)點）之間是一種鏈?zhǔn)江h(huán)結(jié)構(gòu)。所以我們除了可以對B+Tree進(jìn)行主鍵的范圍查找和分頁查找,，還可以從根節(jié)點開始,，進(jìn)行隨機查找。
數(shù)據(jù)庫中的B+Tree索引可以分為聚集索引（clustered index）和輔助索引（secondary index）,。
上面的B+Tree示例圖在數(shù)據(jù)庫中的實現(xiàn)即為聚集索引,，聚集索引的B+Tree中的葉子節(jié)點存放的是整張表的行記錄數(shù)據(jù)，輔助索引與聚集索引的區(qū)別在于輔助索引的葉子節(jié)點并不包含行記錄的全部數(shù)據(jù),，而是存儲相應(yīng)行數(shù)據(jù)的聚集索引鍵,，即主鍵。
當(dāng)通過輔助索引來查詢數(shù)據(jù)時,，InnoDB存儲引擎會遍歷輔助索引找到主鍵,，然后再通過主鍵在聚集索引中找到完整的行記錄數(shù)據(jù)。
不過,，雖然索引可以加快查詢速度,，提高 MySQL 的處理性能，但是過多地使用索引也會造成以下弊端：
創(chuàng)建索引和維護(hù)索引要耗費時間,，這種時間隨著數(shù)據(jù)量的增加而增加,。
除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個索引還要占一定的物理空間,。如果要建立聚簇索引,，那么需要的空間就會更大。
當(dāng)對表中的數(shù)據(jù)進(jìn)行增加,、刪除和修改的時候,，索引也要動態(tài)地維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度,。
注意：索引可以在一些情況下加速查詢,，但是在某些情況下，會降低效率,。
索引只是提高效率的一個因素,，因此在建立索引的時候應(yīng)該遵循以下原則：
在經(jīng)常需要搜索的列上建立索引，可以加快搜索的速度,。
在作為主鍵的列上創(chuàng)建索引,，強制該列的唯一性，并組織表中數(shù)據(jù)的排列結(jié)構(gòu),。
在經(jīng)常使用表連接的列上創(chuàng)建索引,，這些列主要是一些外鍵，可以加快表連接的速度,。
在經(jīng)常需要根據(jù)范圍進(jìn)行搜索的列上創(chuàng)建索引,，因為索引已經(jīng)排序，所以其指定的范圍是連續(xù)的。
在經(jīng)常需要排序的列上創(chuàng)建索引,，因為索引已經(jīng)排序,，所以查詢時可以利用索引的排序，加快排序查詢,。
在經(jīng)常使用 WHERE 子句的列上創(chuàng)建索引,，加快條件的判斷速度。
現(xiàn)在大家知道索引為啥能這么快了吧,，其實就是一句話,，通過索引的結(jié)構(gòu)最大化的減少數(shù)據(jù)庫的IO次數(shù)，畢竟,，一次IO的時間真的是太久了。,。,。
