??????索引齿拂，不光是我們再工作中時常用到的一個名詞凿可，在面試的時候也是逢考必面的知識點状囱，索引可以讓我們的速度提升千百倍效率掰曾，也可以讓我們本來運行很ok的sql變的不那么“和諧”旭蠕，接下來我們就聊聊索引。
一旷坦、什么是索引
??? MySQL官方對索引的定義為：索引(Index)是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)掏熬。
我們可以簡單理解為：快速查找排好序的一種數(shù)據(jù)結(jié)構(gòu)。
或者理解為一本書的目錄秒梅，個人認為重點是“有序”旗芬。
索引的本質(zhì)就是數(shù)據(jù)庫中字段值的復制，該字段稱為索引的關(guān)鍵字捆蜀；
索引也是一張表疮丛，記錄保存了主鍵與索引字段，并指向了實際表數(shù)據(jù)辆它；
索引往往通過復雜的數(shù)據(jù)結(jié)構(gòu)（雙向鏈表誊薄、hash、BTree/B+Tree锰茉、）實現(xiàn)呢蔫；
MyISAM存儲引擎的表支持主索引，InnoDB存儲引擎的表支持聚簇索引(主索引)與非聚簇索引(輔助索引)索引優(yōu)化使用飒筑。
二片吊、主流索引查找算法
線性查找绽昏，是一個鏈表，要搜索的話俏脊，需要從第一個往后一個個找
二分查找全谤，是線性查找的升級，也就是說二分查找是可以用線性查找的數(shù)據(jù)接口联予，但是算法不一樣
二叉樹查找啼县，進一步提高性能材原，引入了二叉樹
平衡二叉樹沸久，二叉樹因為有平衡的問題，又進一步出現(xiàn)了平衡二叉樹
B樹余蟹，在平衡二叉樹之后又發(fā)現(xiàn)了一個問題卷胯，之前的數(shù)據(jù)結(jié)構(gòu)每一個節(jié)點都是一個行數(shù)據(jù)，這樣的話對于磁盤的利用率是有問題的威酒，因為我的數(shù)據(jù)要最終落到磁盤上窑睁，以一個節(jié)點為單位去讀取磁盤效率是很低的
B+樹，B樹效率也有問題葵孤，出現(xiàn)了B+樹担钮，可以理解B+樹是B樹和線性的結(jié)合
二、索引 的分類
從索引存儲結(jié)構(gòu)劃分：B Tree索引尤仍、Hash索引箫津、FULLTEXT全文索引以及R Tree索引
從應用層次劃分：普通索引、唯一索引宰啦、主鍵索引苏遥、復合索引
從鍵值劃分：主鍵、輔助
從數(shù)據(jù)存儲以及索引邏輯關(guān)系劃分：聚集索引赡模、非聚集索引
而Mysql索引主要有兩種結(jié)構(gòu)：B+Tree索引和Hash索引田炭。我們平常所說的索引，如果沒有特別指明漓柑，一般都是指B樹結(jié)構(gòu)組織的索引(B+Tree索引)教硫。
接下來我們就一一介紹一下各個索引名詞：
2.1、BTree 索引
????????BTree? 全稱?Balanced Tree辆布，是一種很普遍的數(shù)據(jù)庫索引結(jié)構(gòu)栋豫，oracle默認的索引類型。
????????其特點是定位高效谚殊、利用率高丧鸯、自我平衡，特別適用于高基數(shù)字段嫩絮，定位單條或小范圍數(shù)據(jù)非常高效丛肢。理論上围肥，使用Btree在億條數(shù)據(jù)與100條數(shù)據(jù)中定位記錄的花銷相同。
演算如下：
讀取root節(jié)點蜂怎，判斷82大于在0-120之間穆刻，走左邊分支。
讀取左邊branch節(jié)點杠步，判斷82大于80且小于等于120氢伟，走右邊分支。
讀取右邊leaf節(jié)點幽歼，在該節(jié)點中找到數(shù)據(jù)82及對應的rowid
使用rowid去物理表中讀取記錄數(shù)據(jù)塊(如果是count或者只select rowid朵锣，則最后一次讀取不需要)
????而由于Btree索引對結(jié)構(gòu)的利用率很高，定位高效甸私。當1千萬條數(shù)據(jù)時诚些，Btree索引也是三層結(jié)構(gòu)(依稀記得億級數(shù)據(jù)才是3層與4層的分水嶺)。定位記錄仍只需要三次I/O皇型，這便是開頭所說的诬烹，100條數(shù)據(jù)和1千萬條數(shù)據(jù)的定位，在btree索引中的花銷是一樣的弃鸦。
Btree索引的自我平衡（平衡擴張）借用下面幾張圖進行說明：
?????新建一個索引绞吁，索引上只會有一個leaf節(jié)點，取名為Node A唬格，不斷的向這個leaf節(jié)點中插入數(shù)據(jù)后家破，直到這個節(jié)點滿；
??????當Node A滿之后西轩，我們再向表中插入一條記錄员舵，此時索引就需要做拆分處理：會新分配兩個數(shù)據(jù)塊NodeB & C，如果新插入的值藕畔，大于當前最大值马僻，則將Node A中的值全部插入Node B中，將新插入的值放到Node C中注服；否則按照5-5比例韭邓，將已有數(shù)據(jù)分別插入到NodeB與C中；
無論采用哪種分割方式溶弟，之前的leaf節(jié)點A女淑，將變成一個root節(jié)點，保存兩個范圍條目辜御，指向B與C鸭你，結(jié)構(gòu)如下圖：
如果當根節(jié)點Node A也滿了，則需要進一步拆分：新建Node E&F&G愉老，將Node A中范圍條目拆分到E&F兩個節(jié)點中场绿，并建立E&F到BCD節(jié)點的關(guān)聯(lián)，向Node G插入索引值嫉入。此時E&F為branch節(jié)點焰盗，G為leaf節(jié)點，A為Root節(jié)點：
在整個擴張過程中咒林，Btree自身總能保持平衡熬拒，Leaf節(jié)點的深度能一直保持一致。
參考文章：http://zsuil.com/?p=1184
2.2映九、B+Tree索引
MySQL數(shù)據(jù)庫索引采用的是B+Tree結(jié)構(gòu)梦湘，在B-Tree結(jié)構(gòu)上做了優(yōu)化改造瞎颗，其特點：
只有葉子節(jié)點包含索引和數(shù)據(jù)
非葉子節(jié)點只存儲索引值
葉子節(jié)點用指針連接件甥，提高區(qū)間訪問性能
對比B樹來說，B+樹范圍查找時哼拔，只需要定位倆個節(jié)點的索引值引有，然后利用葉子節(jié)點指針進行遍歷即可，而B樹需要遍歷范圍內(nèi)所有的節(jié)點數(shù)據(jù)倦逐，倆相對比譬正，B+樹效率更高
2.3、Hash 索引
????Hash索引是基于Hash表實現(xiàn)檬姥，只有查詢條件精確匹配Hash索引中的所有列時曾我，才能夠使用到Hash索引。也就是說健民，Hash索引只能用在等值查詢抒巢，那么范圍和模糊查詢就不可以了；存儲結(jié)構(gòu)如下圖：
????對于Hash索引中的所有列秉犹，存儲引擎都會為每一行計算一個Hash碼蛉谜，Hash索引中儲存的就是Hash碼。
????Hash索引表中保存每一個Hash索引所代表的數(shù)據(jù)行的指針崇堵，由于Hash索引本身只存儲Hash碼型诚，所以Hash索引結(jié)構(gòu)比較緊湊，那么查詢速度比較快鸳劳。
2.2狰贯、FULLTEXT全文索引
全文索引,通過建立倒排索引,可以極大的提升檢索效率,解決判斷字段是否包含的問題.?
例如: 有title字段,需要查詢所有包含 "政府"的記錄. 需要 like "%政府%"方式查詢,查詢速度慢,當查詢包含"政府" OR "中國"的需要是,sql難以簡單滿足.全文索引就可以實現(xiàn)這個功能.
舊版的MySQL的全文索引只能用在MyISAM表格的char、varchar和text的字段上。?
不過新版的MySQL5.6.24上InnoDB引擎也加入了全文索引涵紊，所以具體信息要隨時關(guān)注官網(wǎng)还绘，
--?方式1、創(chuàng)建表的同時創(chuàng)建全文索引CREATE?TABLE?article?(????id?INT?AUTO_INCREMENT?NOT?NULL?PRIMARY?KEY,????title?VARCHAR(200),?????????body?TEXT,?????????FULLTEXT(title,?body)?)?TYPE=MYISAM;?--?方式2.通過?alter?table?的方式來添加ALTER?TABLE?`student`?ADD?FULLTEXT?INDEX?ft_stu_name??(`name`)?;??--?ft_stu_name是索引名栖袋，可以隨便起??--?或者：ALTER?TABLE?`student`?ADD?FULLTEXT?ft_stu_name??(`name`);--?方式3.?直接通過create?index的方式CREATE?FULLTEXT?INDEX?ft_email_name?ON?`student`?(`name`);??--?也可以在創(chuàng)建索引的時候指定索引的長度：CREATE?FULLTEXT?INDEX?ft_email_name?ON?`student`?(`name`(20));
使用全文索引
?使用全文索引的格式：??MATCH?(columnName)?AGAINST?('string');?eg:?????????SELECT?*?FROM?`student`?WHERE?MATCH(`name`)?AGAINST('聰');????????當查詢多列數(shù)據(jù)時：?????????建議在此多列數(shù)據(jù)上創(chuàng)建一個聯(lián)合的全文索引拍顷，否則使用不了索引的。???????SELECT?*?FROM?`student`?WHERE?MATCH(`name`,`address`)?AGAINST('聰?廣東');不知不覺寫到這已經(jīng)2k多字了塘幅，本期我們就寫到這里昔案，下期我們繼續(xù)
探討索引。
…………………………………分割線……………………………
不積跬步电媳，無以至千里踏揣；不積小流，無以成江海匾乓。
我都墨跡這么半天了 捞稿，你不點關(guān)注，不點贊拼缝，不收藏娱局，還不轉(zhuǎn)發(fā)，你想干啥＿制摺Ｋテ搿！继阻！
關(guān)注我耻涛，每天分享一些小知識點。分享自己的小心得瘟檩，包含但不限于初抹缕、中、高級面試題呦Ｄ痢Ｗ垦小！
