點擊上方 "程序員小樂"關注, 星標或置頂一起成長
每天凌晨00點00分, 第一時間與你相約
每日英文
A single hand that wipes tears during failures is much better than countless hands that come together to clap on success.
失敗時有人伸出一隻手來為你擦淚，會好過成功時無數人伸手為你鼓掌。
每日掏心話
當看破一切的時候才知道，其實失去比擁有更踏實。
來自：NebulaGraph | 責編：樂樂
鏈接：my.oschina.net/u/4169309/blog/3216614
程序員小樂(ID:study_tech)第 826 次推文 圖片來自百度
往日回顧：Google 出品的 Java 編碼規範，強烈推薦，權威又科學！
正文
之前有過一次面試，關於MySQL索引的原理及使用被面試官懟的體無完膚，立志要總結一番，然後一直沒有時間（其實是懶……），準備好了嗎？
索引是什麼？
數據庫索引，是數據庫管理系統(DBMS)中一個排序的數據結構，它可以對數據庫表中一列或多列的值進行排序，以協助更加快速的訪問數據庫表中特定的數據。通俗的說，我們可以把數據庫索引比做是一本書前面的目錄，它能加快數據庫的查詢速度。
為什麼需要索引？
思考：如何在一個圖書館中找到一本書？設想一下，假如在圖書館中沒有其他輔助手段，只能一條道走到黑，一本書一本書的找，經過3個小時的連續查找，終於找到了你需要看的那本書，但此時天都黑了。為了避免這樣的事情，每個圖書館才都配備了一套圖書館管理系統，大家要找書籍的話，先在系統上查找到書籍所在的房屋編號、圖書架編號還有書在圖書架幾層的那個方位，然後就可以直接大搖大擺的去取書了，就可以很快速的找到我們所需要的書籍。索引就是這個原理，它可以幫助我們快速的檢索數據。
一般的應用系統對數據庫的操作，遇到最多、最容易出問題是一些複雜的查詢操作，當數據庫中數據量很大時，查找數據就會變得很慢，這樣就很影響整個應用系統的效率，我們就可以使用索引來提高數據庫的查詢效率。
B-Tree和B+Tree
目前大部分數據庫系統及文件系統都採用B-Tree或其變種B+Tree作為索引結構， 我在這裡分別講一下：
B-Tree
即B樹，注意（不是B減樹），B樹是一種多路搜索樹。使用B-Tree結構可以顯著減少定位記錄時所經歷的中間過程，從而加快存取速度。
B-Tree有如下一些特徵：
定義任意非葉子結點最多隻有M個子節點，且M>2。
根結點的兒子數為[2, M]。
除根結點以外的非葉子結點的兒子數為[M/2, M]， 向上取整 。
每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）。
非葉子結點的關鍵字個數=指向兒子的指針個數-1。
非葉子結點的關鍵字：K[1], K[2], …, K[M-1]，且K[i] <= K[i+1]。
非葉子結點的指針：P[1], P[2], …,P[M]（其中P[1]指向關鍵字小於K[1]的子樹，P[M]指向關鍵字大於K[M-1]的子樹，其它P[i]指向關鍵字屬於(K[i-1], K[i])的子樹）。
所有葉子結點位於同一層。
有關b樹的一些特性：
關鍵字集合分佈在整顆樹的所有結點之中；
任何一個關鍵字出現且只出現在一個結點中；
搜索有可能在非葉子結點結束；
其搜索性能等價於在關鍵字全集內做一次二分查找。
B樹的搜索：從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬範圍的兒子結點；重複執行這個操作，直到所對應的節點指針為空，或者已經是是葉子結點。
例如下面一個B樹，那麼查找元素43的過程如下：
根據根節點指針找到18、37所在節點，把此節點讀入內存，進行第一次磁盤IO，此時發現43>37，找到指針p3。
根據指針p3，找到42、51所在節點，把此節點讀入內存，進行第二次磁盤IO，此時發現42<43<51，找到指針p2。
根據指針p2，找到43、46所在節點，把此節點讀入內存，進行第三次磁盤IO，此時我們就已經查到了元素43。
在此過程總共進行了三次磁盤IO。
B+Tree
B+Tree屬於B-Tree的變種。與B-Tree相比，B+Tree有以下不同點：
有n棵子樹的非葉子結點中含有n個關鍵字（B樹是n-1個），即非葉子結點的子樹指針與關鍵字個數相同。這些關鍵字不保存數據，只用來索引，所有數據都保存在葉子節點（B樹是每個關鍵字都保存數據）。
所有的葉子結點中包含了全部關鍵字的信息，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序鏈接。
所有的非葉子結點可以看成是葉子節點的索引部分。
同一個數字會在不同節點中重複出現，根節點的最大元素就是b+樹的最大元素。
相對B樹，B+樹做索引的優勢
B+樹的磁盤IO代價更低： B+樹非葉子節點沒有指向數據行的指針，所以相同的磁盤容量存儲的節點數更多，相應的IO讀寫次數肯定減少了。
B+樹的查詢效率更加穩定：由於所有數據都存於葉子節點。所有關鍵字查詢的路徑長度相同，每一個數據的查詢效率相當。
所有的葉子節點形成了一個有序鏈表，更加便於查找。
關於MySQL的兩種常用存儲引擎MyISAM和InnoDB的索引均以B+樹作為數據結構，二者卻有不同（這裡只說二者索引的區別）。
MyISAM索引和Innodb索引的區別
MyISAM使用B+樹作為索引結構，葉節點葉節點的data域保存的是存儲數據的地址，主鍵索引key值唯一，輔助索引key可以重複，二者在結構上相同。 因此，MyISAM中索引檢索的算法為首先按照B+Tree搜索算法搜索索引，如果要找的Key存在，則取出其data域的值，然後以data域的值為地址，去讀取相應數據記錄 。因此，索引文件和數據文件是分開的，從索引中檢索到的是數據的地址，而不是數據。
Innodb也是用B+樹作為索引結構，但具體實現方式卻與MyISAM截然不同，首先，數據表本身就是按照b+樹組織，所以數據文件本身就是主鍵索引文件。葉節點key值為數據表的主鍵，data域為完整的數據記錄，因此InnoDB表數據文件本身就是主鍵索引(這也就是MyISAM可以允許沒有主鍵，但是Innodb必須有主鍵的原因）。第二個與MyISAM索引的不同是InnoDB的輔助索引的data域存儲相應數據記錄的主鍵值而不是地址。換句話說，InnoDB的所有輔助索引都引用主鍵作為data域。
索引類型
普通索引：（由關鍵字KEY或INDEX定義的索引）的唯一任務是加快對數據的訪問速度。
唯一索引： 普通索引允許被索引的數據列包含重複的值，而唯一索引不允許，但是可以為null。所以任務是保證訪問速度和避免數據出現重複。
主鍵索引：在主鍵字段創建的索引，一張表只有一個主鍵索引。
組合索引：多列值組成一個索引，專門用於組合搜索。
全文索引：對文本的內容進行分詞，進行搜索。（MySQL5.6及以後的版本，MyISAM和InnoDB存儲引擎均支持全文索引。）
索引的使用策略及優缺點
使用索引
主鍵自動建立唯一索引。
經常作為查詢條件在WHERE或者ORDER BY 語句中出現的列要建立索引。
查詢中與其他表關聯的字段，外鍵關係建立索引。
經常用於聚合函數的列要建立索引，如min()，max()等的聚合函數。
不使用索引
經常增刪改的列不要建立索引。
有大量重複的列不建立索引。
表記錄太少不要建立索引，因為數據較少，可能查詢全部數據花費的時間比遍歷索引的時間還要短，索引就可能不會產生優化效果 。
最左匹配原則
建立聯合索引的時候都會默認從最左邊開始，所以索引列的順序很重要，建立索引的時候就應該把最常用的放在左邊，使用select的時候也是這樣，從最左邊的開始，依次匹配右邊的。
優點
可以保證數據庫表中每一行的數據的唯一性。
可以大大加快數據的索引速度。
加速表與表之間的連接。
可以顯著的減少查詢中分組和排序的時間。
缺點
創建索引和維護索引要耗費時間，這種時間隨著數據量的增加而增加。
索引需要佔物理空間，除了數據表佔用數據空間之外，每一個索引還要佔用一定的物理空間，如果需要建立聚簇索引，那麼需要佔用的空間會更大，其實建立索引就是以空間換時間。
表中的數據進行增、刪、改的時候，索引也要動態的維護，這就降低了維護效率。
驗證索引是否能夠提升查詢性能
創建測試表index_test
使用python腳本程序通過pymsql模塊，向表中添加十萬條數據
import pymysql
def main():
# 創建Connection連接
conn = pymysql.connect(host='localhost',
port=3306,
database='db_test',
user='root',
password='deepin',
charset='utf8')
# 獲得Cursor對象
cursor = conn.cursor()
# 插入10萬次數據
for i in range(100000):
cursor.execute("insert into index_test values('haha-%d')" % i)
# 提交數據
conn.commit()
if __name__ == "__main__":
main()
在mysql終端開啟運行時間監測：set profiling=1;
查找第1萬條數據ha-99999
select * from index_test where name='haha-99999';
查看執行的時間：
show profiles;
為表index_test的name列創建索引：
create index name_index on index_test(name(10));
再次執行查詢語句、查看執行的時間：
可以看出合適的索引確實可以明顯提高某些字段的查詢效率。
最後，感謝女朋友在生活中，工作上的包容、理解與支持 ！
歡迎在留言區留下你的觀點，一起討論提高。如果今天的文章讓你有新的啟發，學習能力的提升上有新的認識，歡迎轉發分享給更多人。
猜你還想看
阿里、騰訊、百度、華為、京東最新面試題彙集
如何更好的使用Java異常，看這篇就對了！
Java IO使用的四種模式
（三）SpringBoot+SpringCloud —— 高可用的Eureka註冊中心
關注訂閱號「程序員小樂」，收看更多精彩內容
嘿，你在看嗎？
閱讀更多 程序員小樂 的文章
