数据库索引的实现原理及查询优化
MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效獲取數據的數據結構。
使用索引的目的在于提高查詢效率，這篇文章梳理一下索引的實現原理和應用。
?
不同的存儲引擎索引實現的數據結構不同
MySQL支持諸多存儲引擎，而各種存儲引擎對索引的支持也各不相同，因此MySQL數據庫支持多種索引類型，如B-Tree索引，哈希索引，全文索引等，
主要存儲引擎有MyISAM、InnoDB、MEMORY和MERGE等，在創建表到時候通過engine=或type=來指定所要使用到引擎，
來查看指定表的引擎。
MyISAM不支持事務，也不支持外鍵，訪問速度快，對事務完整性沒有要求或者以SELECT、INSERT為主的應用可以使用這個引擎來創建表，memory數據表使用散列索引，
InnoDB存儲引擎則提供了具有提交、回滾和崩潰恢復能力的事務安全。但是對比MyISAM的存儲引擎，InnoDB寫的處理效率差一些并且會占用更多的磁盤空間以保留數據和索引。
這里只關注應用最廣泛的InnoDB的B-Tree索引。
?
索引實現的B-Tree結構
數據庫索引是通過B-Tree實現的，但是為什么使用B-Tree而不是使用紅黑樹或者其他的查找數據結構呢，
通過對樹結構的回顧分析一下。
紅黑樹（Red-Black Tree）是二叉搜索樹（Binary Search Tree）的一種改進。我們知道二叉搜索樹在最壞的情況下可能會變成一個鏈表（當所有節點按從小到大的順序依次插入后）。而紅黑樹在每一次插入或刪除節點之后都會花O（log N）的時間來對樹的結構作修改，以保持樹的平衡。也就是說，紅黑樹的查找方法與二叉搜索樹完全一樣；插入和刪除節點的的方法前半部分節與二叉搜索樹完全一樣，而后半部分添加了一些修改樹的結構的操作。
紅黑樹的每個節點上的屬性除了有一個key、3個指針：parent、lchild、rchild以外，還多了一個屬性：color。它只能是兩種顏色：紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質之外，還具有以下4點性質：
1. 根節點是黑色的。
2. 空節點是黑色的（紅黑樹中，根節點的parent以及所有葉節點lchild、rchild都不指向NULL，而是指向一個定義好的空節點）。
3. 紅色節點的父、左子、右子節點都是黑色。
4. 在任何一棵子樹中，每一條從根節點向下走到空節點的路徑上包含的黑色節點數量都相同。
B-Tree又叫平衡多路查找樹。B-樹是為了磁盤或其它存儲設備而設計的一種多叉平衡查找樹，相對于二叉，B樹每個內結點有多個分支，即多叉。與紅黑樹很相似，但在降低磁盤I/0操作方面要更好一些。
為什么使用B-Tree而不是使用紅黑樹或者其他的查找數據結構，紅黑樹多用在內部排序，即全部在內存中的，C++的STL中map和set的內部實現就是紅黑樹，Java集合框架里HashSet和HashTree也是使用紅黑樹實現，
B樹多用在內存里放不下，大部分數據存儲在外存上時。因為B樹層數少，因此可以確保每次操作，讀取磁盤的次數盡可能的少。
?
索引創建的幾個原則
（1）適合索引的列是出現在WHERE 子句中的列
最適合索引的列是出現在WHERE 子句中的列，或連接子句中指定的列，而不是出現在SELECT 關鍵字后的選擇列表中的列。
（2）使用惟一索引
考慮某列中值的分布。對于惟一值的列，索引的效果最好，而具有多個重復值的列，其索引效果最差。例如，存放年齡的列具有不同值，很容易區分 各行。而用來記錄性別的列，只含有“ M”和“F”，則對此列進行索引沒有多大用處。
（3）使用短索引
如果對串列進行索引，應該指定一個前綴長度，只要有可能就應該這樣做。例如，如果有一個CHAR(200) 列，如果在前10 個或20 個字符內，多數值是惟一的，那么就不要對整個列進行索引。對前10 個或20 個字符進行索引能夠節省大量索引空間，也可能會使查詢更快。較小的索引涉及的磁盤I/O 較少，較短的值比較起來更快。更為重要的是，對于較短的鍵值，索引高速緩存中的塊能容納更多的鍵值，因此，MySQL也可以在內存中容納更多的值。這增加 了找到行而不用讀取索引中較多塊的可能性。（當然，應該利用一些常識。如僅用列值的第一個字符進行索引是不可能有多大好處的，因為這個索引中不會有許多不 同的值。）
（4）利用最左前綴
在創建一個n 列的索引時，實際是創建了MySQL可利用的n 個索引。多列索引可起幾個索引的作用，因為可利用索引中最左邊的列集來匹配行。這樣的列集稱為最左前綴。（這與索引一個列的前綴不同，索引一個列的前綴是利用該的前n 個字符作為索引值。）
（5）不要過度索引
不要以為索引“越多越好”，什么東西都用索引是錯的。每個額外的索引都要占用額外的磁盤空間，并降低寫操作的性能，這一點我們前面已經介紹 過。在修改表的內容時，索引必須進行更新，有時可能需要重構，因此，索引越多，所花的時間越長。如果有一個索引很少利用或從不使用，那么會不必要地減緩表 的修改速度。此外，MySQL在生成一個執行計劃時，要考慮各個索引，這也要費時間。創建多余的索引給查詢優化帶來了更多的工作。索引太多，也可能會使 MySQL選擇不到所要使用的最好索引。只保持所需的索引有利于查詢優化。如果想給已索引的表增加索引，應該考慮所要增加的索引是否是現有多列索引的最左 索引。如果是，則就不要費力去增加這個索引了，因為已經有了。
（6）考慮在列上進行的比較類型。
索引可用于“ <”、“ < = ”、“ = ”、“ > =”、“ > ”和BETWEEN 運算。在模式具有一個直接量前綴時，索引也用于LIKE 運算。如果只將某個列用于其他類型的運算時（如STRCMP( )），對其進行索引沒有價值。
索引并不是越多越好，索引固然可以提高相應的 select 的效率，但同時也降低了 insert 及 update 的效率，因為 insert 或 update 時有可能會重建索引，所以怎樣建索引需要慎重考慮，視具體情況而定。一個表的索引數最好不要超過6個，若太多則應考慮一些不常使用到的列上建的索引是否有必要。
?
?
創建索引的時機
（1）什么時候創建索引
較頻繁地作為查詢條件的字段，也就是說最適合索引的列是出現在WHERE 子句中的列，或連接子句中指定的列，而不是出現在SELECT 關鍵字后的選擇列表中的列。
（2）什么時候不創建索引
表記錄太少：
如果一個表只有5條記錄，采用索引去訪問記錄的話，那首先需訪問索引表，再通過索引表訪問數據表，一般索引表與數據表不在同一個數據塊，這種情況下ORACLE至少要往返讀取數據塊兩次。而不用索引的情況下ORACLE會將所有的數據一次讀出，處理速度顯然會比用索引快。
唯一性太差的字段：如狀態字段、類型字段。那些只存儲固定幾個值的字段，例如用戶登錄狀態、消息的status等。
這個涉及到了索引掃描的特性。例如：通過索引查找鍵值為A和B的某些數據，通過A找到某條相符合的數據，這條數據在X頁上面，然后繼續掃描，又發現符合A的數據出現在了Y頁上面，那么存儲引擎就會丟棄X頁面的數據，然后存儲Y頁面上的數據，一直到查找完所有對應A的數據，然后查找B字段，發現X頁面上面又有對應B字段的數據，那么他就會再次掃描X頁面，等于X頁面就會被掃描2次甚至多次。以此類推，所以同一個數據頁可能會被多次重復的讀取，丟棄，在讀取，這無疑給存儲引擎極大地增加了IO的負擔。
更新太頻繁地字段不適合創建索引：
當你為這個字段創建索引時候，當你再次更新這個字段數據時，數據庫會自動更新他的索引，所以當這個字段更新太頻繁地時候那么就是不斷的更新索引。
如果一個字段同一個時間段內被更新多次，那么不能為他建立索引。
?
索引失效的幾種情況
（1）盡量避免在 where 子句中對字段進行 null 值判斷，否則將導致引擎放棄使用索引而進行全表掃描，如：
select id from t where num is null
可以在num上設置默認值0，確保表中num列沒有null值，然后這樣查詢：
select id from t where num=0
（2）盡量避免在 where 子句中使用!=或<>操作符，否則將引擎放棄使用索引而進行全表掃描。
（3）盡量避免在 where 子句中使用 or 來連接條件，否則將導致引擎放棄使用索引而進行全表掃描，
可以這樣查詢：
select id from t where num=10 union all select id from t where num=20
（4）in 和 not in 也要慎用，否則會導致全表掃描，如：
select id from t where num in(1,2,3)對于連續的數值，能用 between 就不要用 in 了：
select id from t where num between 1 and 3下面的查詢也將導致全表掃描：
select id from t where name like '%abc%'
若要提高效率，可以考慮全文檢索。
（5）盡量避免在where子句中對字段進行函數操作，這將導致引擎放棄使用索引而進行全表掃描。如：
select id from t where substring(name,1,3)='abc'--name以abc開頭的id select id from t where datediff(day,createdate,'2005-11-30')=0--‘2005-11-30’生成的id應改為:
select id from t where name like 'abc%' select id from t where createdate>='2005-11-30' and createdate<'2005-12-1'索引失效的情況還有很多，其他的還有使用<>或者單獨的單獨的>,<；當變量采用的是times變量，而表的字段采用的是date變量時等
?
使用explains優化慢查詢
MySQL的Explain命令用于查看執行效果，顯示了mysql如何使用索引來處理select語句以及連接表。
可以幫助選擇更好的索引和寫出更優化的查詢語句。
explain的語法如下，在select語句前加上explain就可以：
EXPLAIN列的解釋：
table：顯示這一行的數據是關于哪張表的
type：這是重要的列，顯示連接使用了何種類型。從最好到最差的連接類型為const、eq_reg、ref、range、index和ALL
possible_keys：顯示可能應用在這張表中的索引。如果為空，沒有可能的索引。可以為相關的域從WHERE語句中選擇一個合適的語句
key： 實際使用的索引。如果為NULL，則沒有使用索引。很少的情況下，MYSQL會選擇優化不足的索引。這種情況下，可以在SELECT語句中使用USE INDEX（indexname）來強制使用一個索引或者用IGNORE INDEX（indexname）來強制MYSQL忽略索引
key_len：使用的索引的長度。在不損失精確性的情況下，長度越短越好
ref：顯示索引的哪一列被使用了，如果可能的話，是一個常數
rows：MYSQL認為必須檢查的用來返回請求數據的行數
Extra：關于MYSQL如何解析查詢的額外信息。
?
好文書簽?
MySQL索引及查詢優化
SQL優化避免索引失效
總結
以上是生活随笔為你收集整理的数据库索引的实现原理及查询优化的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Ajax学习心得
- 下一篇： 模拟键盘 键盘虚拟代码