索引（index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。常見的查詢算法：順序查找、二分查找、二叉樹查找、哈希散列、分塊查找、B樹。
1）哈希算法：就是把任意長度值（key）通過散列算法變成固定長度的key地址，通過這個(gè)地址進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。它通過關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找速度。時(shí)間復(fù)雜度為O(1)，尋址查詢，不適用于范圍查詢，無法排序。
2）二叉樹：它的左子節(jié)點(diǎn)值比父節(jié)點(diǎn)值小，右子節(jié)點(diǎn)值比父節(jié)點(diǎn)值大。時(shí)間復(fù)雜度為O(logN)，缺點(diǎn)：不平衡二叉樹。
3）B樹：度（degree）-節(jié)點(diǎn)的數(shù)據(jù)存儲個(gè)數(shù)；葉節(jié)點(diǎn)具有相同的深度且指針為空；葉節(jié)點(diǎn)的數(shù)據(jù)key從左到右遞增排序。
4）B+樹：真實(shí)的數(shù)據(jù)存在于葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)不存儲真實(shí)的數(shù)據(jù)，只存儲指引搜索方向的數(shù)據(jù)項(xiàng)。
常見的索引原則：
1）選擇唯一性索引：唯一性索引的值是唯一的，可以更快速地通過該索引來確定某條記錄。
2）為常作為查詢條件的字段建立索引、為經(jīng)常需要排序、分組和聯(lián)合操作的字段建立索引。
3）限制索引的數(shù)目：越多的索引，會使更新表變得很浪費(fèi)時(shí)間。
4）盡量使用數(shù)據(jù)量少的索引：如果索引的值很長，那么查詢的速度會受到影響。
5）盡量使用前綴來索引：如果索引字段的值很長，最好使用值得前綴來索引。
6）刪除不再使用或很少使用的索引。
7）最左匹配原則，是非常重要的原則。
8）盡量選擇區(qū)分度高的列作為索引。
9）索引列不能參與運(yùn)算，帶函數(shù)的查詢不能參與索引。
10）盡量的擴(kuò)展索引，不要新建索引。
創(chuàng)建索引
1）創(chuàng)建表時(shí)，創(chuàng)建索引：
create table 表名 (字段 數(shù)據(jù)類型 , [unique | fulltext | spatial][index | key] 索引名稱 (被索引字段名[length]) [asc | desc] );
1 CREATE TABLE book ( 2 bookid INT NOT NULL, 3 bookname VARCHAR(255)NOT NULL, 4 year_publication YEAR NOT NULL, 5 UNIQUE INDEX UniquId(id), ##唯一索引 6 INDEX(year_publication), ##普通索引 7 INDEX SingleIdx(bookname(20)), ##單列索引 8 INDEX MultiIdx(bookid,bookname(100)), ##組合索引 9 FULLTEXT INDEX FullTextIdx(bookname)， ##全文索引（只支持MyISAM—>engine=MyISAM）10 g GEOMETRY NOT NULL,11 SPATIAL INDEX spatIdx(g) ##空間索引（存儲引擎必須為MyISAM且空間類型的字段為空值）12 );2）在已經(jīng)存在的表上創(chuàng)建索引：
a. 使用 alter table 創(chuàng)建索引：alter table 表名 add [unique | fulltext | spatial] [index] 索引名稱 (被索引字段名[length]) [asc | desc];
例：alter table book add index BknameIdx(bookname(30));
b. 使用 create index 創(chuàng)建索引：create [unique | fulltext | spatial] [index] 索引名稱 on 表名 (被索引字段名[length]) [asc | desc];
刪除索引
1）使用 alter table 刪除索引：alter table 表名 drop index 索引名稱;
例：alter table book drop index BknameIdx;
2）使用 drop index 刪除索引：drop index 索引名稱 on 表名;
查看索引
show index from 表名;
索引的分類：唯一索引/非唯一索引、主鍵索引（主索引）、聚集索引/非聚集索引、組合索引。
1）唯一索引是在表上一個(gè)或者多個(gè)字段組合建立的索引，這個(gè)或者這些字段的值組合起來在表中不可以重復(fù)。
如下表中，為“學(xué)號”建立索引：
學(xué)號 姓名
------------------------------------
001 張三
002 李四
2）非唯一索引是在表上一個(gè)或者多個(gè)字段組合建立的索引，這個(gè)或者這些字段的值組合起來在表中可以重復(fù)，不要求唯一。
如下表，為Score建立索引，可不唯一：
Score Name
98 張三
98 李四
3）主鍵索引（主索引）是唯一索引的特定類型。表中創(chuàng)建主鍵時(shí)自動創(chuàng)建的索引。一個(gè)表只能建立一個(gè)主索引。
4）聚集索引（聚簇索引）：表中記錄的物理順序與鍵值的索引順序相同。一個(gè)表只能有一個(gè)聚集索引。
擴(kuò)展：聚集索引和非聚集索引的區(qū)別？分別在什么情況下使用？
聚集索引和非聚集索引的根本區(qū)別是表中記錄的物理順序和索引的排列順序是否一致。
聚集索引的表中記錄的物理順序與索引的排列順序一致。
優(yōu)點(diǎn)是查詢速度快，因?yàn)橐坏┚哂械谝粋€(gè)索引值的記錄被找到，具有連續(xù)索引值的記錄也一定無力的緊跟其后。
缺點(diǎn)是對表進(jìn)行修改速度較慢，這是為了保持表中的記錄的物理順序與索引順序一致，而把記錄插入到數(shù)據(jù)頁的相應(yīng)位置，必須在數(shù)據(jù)頁中進(jìn)行數(shù)據(jù)重排，降低了執(zhí)行速度。在插入記錄時(shí)數(shù)據(jù)文件為了維持B+樹的特性而頻繁的分裂調(diào)整，十分低效。
建議使用聚集索引的場合為：
a. 某列包含了小數(shù)目的不同值；
b. 排序和范圍查找；
非聚集索引的記錄的物理順序和索引的順序不一致。
其他方面的區(qū)別：
a. 聚集索引和非聚集索引都采用了B+樹結(jié)構(gòu)，但非聚集索引的葉子層并不與實(shí)際的數(shù)據(jù)頁相重疊，而采用葉子層包含一個(gè)指向表中的記錄在數(shù)據(jù)頁中的指針的方式。聚集索引的葉子節(jié)點(diǎn)就是數(shù)據(jù)節(jié)點(diǎn)，而非聚集索引的葉子節(jié)點(diǎn)仍然是索引節(jié)點(diǎn)。
b. 非聚集索引添加記錄時(shí)，不會引起數(shù)據(jù)順序的重組。
看上去聚簇索引的效率明顯要低于非聚簇索引，因?yàn)槊看问褂幂o助索引檢索都要經(jīng)過兩次B+樹查找，這不是多此一舉嗎？聚簇索引的優(yōu)勢在哪？
由于行數(shù)據(jù)和葉子節(jié)點(diǎn)存儲在一起，這樣主鍵和行數(shù)據(jù)是一起被載入內(nèi)存的，找到葉子節(jié)點(diǎn)就可以立刻將行數(shù)據(jù)返回了，如果按照主鍵id來組織數(shù)據(jù)，獲得數(shù)據(jù)更快。
輔助索引使用主鍵作為“指針”，而不是使用地址值作為指針的好處是，減少了當(dāng)出現(xiàn)行移動或者數(shù)據(jù)頁分裂時(shí)，輔助索引的維護(hù)工作，Innodb在移動行時(shí)無需更新輔助索引中的這個(gè)“指針”。也就是說行的位置會隨著數(shù)據(jù)庫里的數(shù)據(jù)的修改而發(fā)生變化，使用聚簇索引就可以保證不管這個(gè)主鍵B+樹的節(jié)點(diǎn)如何變化，輔助索引樹都不受影響。
建議使用非聚集索引的場合為：
a. 此列包含了大數(shù)目的不同值；
b. 頻繁更新的列；
5）組合索引（聯(lián)合索引）：基于多個(gè)字段而創(chuàng)建的索引就稱為組合索引?！ ?/span>
創(chuàng)建索引
create index idx1 on table1(col1,col2,col3);
查詢
select * from table1 where col1=A and col2 =B and col3 = C;
舉例說明：給出一個(gè)多列索引(username,password,age)，當(dāng)三列在where中出現(xiàn)的順序如(username,password,age)、(username,password)、(username)才能用到索引，如下面幾個(gè)順序（password,age）、(password)、(age)---這三者不從username開始，（username,age）---斷層，少了password，都無法利用到索引。因?yàn)锽+樹多列索引保存的順序是按照索引創(chuàng)建的順序，檢索索引時(shí)按照此順序檢索。
數(shù)據(jù)庫索引的原理（實(shí)現(xiàn)）
MyISAM索引實(shí)現(xiàn)
MyISAM引擎使用B+樹作為索引結(jié)構(gòu)，葉子節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址。在MyISAM中，主索引和輔助索引在結(jié)構(gòu)上沒有任何區(qū)別，只是主索引要求key是唯一的，而輔助索引的key可以重復(fù)。
MyISAM中索引檢索的算法為首先按照B+樹搜索算法搜索索引，如果指定的key存在，則取出其data域的值，然后以data域的值為地址，讀取相應(yīng)數(shù)據(jù)記錄。MyISAM的索引方式也叫做“非聚集索引”。
InnoDB索引實(shí)現(xiàn)
雖然InnoDB也使用B+樹作為索引結(jié)構(gòu)，但具體實(shí)現(xiàn)方式卻與其截然不同。
第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件。在InnoDB中，表數(shù)據(jù)文件本身就是B+樹組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉結(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄。這種索引也叫做聚集索引。
第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲相應(yīng)記錄主鍵的值而不是地址?！ ?/span>
索引的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：大大加快了數(shù)據(jù)的檢索速度；
創(chuàng)建唯一性索引，保證數(shù)據(jù)庫表中每行數(shù)據(jù)的唯一性；
加速表和表之間的連接；
在使用分組和排序子句進(jìn)行數(shù)據(jù)檢索時(shí)，可以顯著減少查詢中分組和排序的時(shí)間。
缺點(diǎn)：索引需要占物理空間；
當(dāng)對表中的數(shù)據(jù)進(jìn)行增加、刪除和修改時(shí)，索引也要動態(tài)的維護(hù)，降低了數(shù)據(jù)的維護(hù)速度。
輔助索引
聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效，但是輔助索引搜索需要搜索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄。
為什么不建議使用過長的字段作為主鍵？
因?yàn)樗休o助索引都引用主索引，過長的主索引會令輔助索引變得過大。
B樹的查找過程
如上圖所示，如果要查找數(shù)據(jù)項(xiàng)為29，那么首先會把磁盤塊1由磁盤加載到內(nèi)存，此時(shí)發(fā)生一次IO，在內(nèi)存中用二分查找確定29在17和35之間，鎖定磁盤塊1的P2指針，內(nèi)存時(shí)間因?yàn)榉浅６蹋ㄏ啾却疟P的IO）可以忽略不計(jì)，通過磁盤塊1的P2指針的磁盤地址把磁盤塊3由磁盤加載到內(nèi)存，發(fā)生第二次IO，29在26和30之間，鎖定磁盤塊3的P2指針，通過指針加載磁盤塊8到內(nèi)存，發(fā)生第三次IO，同時(shí)內(nèi)存中做二分查找找到29，結(jié)束查詢，總計(jì)三次IO。真實(shí)的情況是，3層的B+樹可以表示上百萬的數(shù)據(jù)，如果上百萬的數(shù)據(jù)查找只需要三次IO，性能提高將是巨大的，如果沒有索引，每個(gè)數(shù)據(jù)項(xiàng)都要發(fā)生一次IO，那么總共需要百萬此次的IO，顯然成本非常高。
注意：當(dāng)B+樹的數(shù)據(jù)項(xiàng)是復(fù)合的數(shù)據(jù)結(jié)構(gòu)（建立的是復(fù)合索引），比如(name,age,sex)的時(shí)候，B+樹是按照從左到右的順序建立搜索樹的，比如當(dāng)(張三,20,F)這樣的數(shù)據(jù)來檢索的時(shí)候，B+樹會優(yōu)先比較name來確定下一步的搜索方向，如果name相同再依次比較age和sex，最后得到檢索的數(shù)據(jù)；但當(dāng)(20,F)這樣的沒有name的數(shù)據(jù)來的時(shí)候，B+樹就不知道下一步該查哪個(gè)節(jié)點(diǎn)，因?yàn)榻⑺阉鳂涞臅r(shí)候name就是第一個(gè)比較因子，必須要先根據(jù)name來搜索才能知道下一步去哪里查詢。比如當(dāng)(張三,F)這樣的數(shù)據(jù)來檢索時(shí)，B+樹可以用name來指定搜索方向，但下一個(gè)字段age的缺失，所以只能把名字等于張三的數(shù)據(jù)都找到，然后再匹配性別是F的數(shù)據(jù)了，這個(gè)是非常重要的性質(zhì)，即索引的最左匹配特性。注意：B+tree多列索引保存的順序是按照索引創(chuàng)建的順序，檢索索引時(shí)按照此順序檢索。
最左匹配原則中where字句有or出現(xiàn)還是會遍歷全表。
性別字段為什么不適合加索引？從B+樹原理解釋。
盡量選擇區(qū)分度高的字段作為索引，區(qū)分度的公式是count(distince col)/count(*)，表示字段不重復(fù)的比例，比例越高我們掃描的記錄數(shù)越少，唯一鍵的區(qū)分度為1，而一些狀態(tài)、性別字段可能在大數(shù)據(jù)面前區(qū)分度為0。在性別字段上增加索引，并不能明顯加快索引速度。
MySQL的B+樹索引的優(yōu)點(diǎn)？為什么不用二叉樹？B樹和B+樹為什么比紅黑樹更合適？
數(shù)據(jù)庫文件很大，需要存儲到磁盤上，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤IO的讀取次數(shù)。
1）高度原因
B+樹中的每個(gè)節(jié)點(diǎn)可以包含大量的關(guān)鍵字，這樣樹的深度降低了，所以任何關(guān)鍵字的查找必須走一條從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路，所有關(guān)鍵字查詢的路徑長度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)，這就意味著查找一個(gè)元素只要很少節(jié)點(diǎn)從外存磁盤中讀入內(nèi)存，很快訪問到要查詢的數(shù)據(jù)，減少了磁盤IO的讀取次數(shù)。
2）磁盤預(yù)讀原理和局部性原理
將一個(gè)節(jié)點(diǎn)的大小設(shè)為等于一個(gè)頁（16k），這樣每個(gè)節(jié)點(diǎn)只需要一次IO就可以完全載入。
