原理： http://blog.csdn.net/cangchen/article/details/44818485 http://blog.csdn.net/kennyrose/article/details/7532032 http://www.cnblogs.com/qinpengming/p ...
原理：
http://blog.csdn.net/cangchen/article/details/44818485 http://blog.csdn.net/kennyrose/article/details/7532032 http://www.cnblogs.com/qinpengming/p/5897194.html本質：
為什麼使用B+樹？言簡意賅，就是因為： 1.文件很大，不可能全部存儲在記憶體中，故要存儲到磁碟上 2.索引的結構組織要儘量減少查找過程中磁碟I/O的存取次數（為什麼使用B-/+Tree，還跟磁碟存取原理有關。） 3.局部性原理與磁碟預讀，預讀的長度一般為頁（page）的整倍數，（在許多操作系統中，頁得大小通常為4k） 4.資料庫系統巧妙利用了磁碟預讀原理，將一個節點的大小設為等於一個頁，這樣每個節點只需要一次I/O就可以完全載入，(由於節點中有兩個數組，所以地址連續)。而紅黑樹這種結構，h明顯要深的多。由於邏輯上很近的節點（父子）物理上可能很遠，無法利用局部性 Mysql存儲引擎的區別： MyISAM :Mysql 預設的存儲引擎，如果應用是以讀操作和寫操作為主，只有很少的更新，刪除操作，並對事物的完整性要求不是很高。其優勢是訪問的速度快 InnoDB: 提供了具有提交，回滾和崩潰恢復能力的事物安全，但是對MyISAM 寫的處理效率差一些並且會占用更多的磁碟空間。 InnoDB索引和MyISAM索引的區別： 一是主索引的區別，InnoDB的數據文件本身就是索引文件。而MyISAM的索引和數據是分開的。 二是輔助索引的區別：InnoDB的輔助索引data域存儲相應記錄主鍵的值而不是地址。而MyISAM的輔助索引和主索引沒有多大區別。 Innodb 存儲引擎的 B-Tree 索引實際使用的存儲結構實際上是B+Tree ，也就是在 B-Tree 數據結構的基礎上做了很小的改造，在每一個Leaf Node 上面出了存放索引鍵的相關信息之外，還存儲了指向與該 Leaf Node 相鄰的後一個 LeafNode 的指針信息（增加了順序訪問指針），這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。 MyISAM的索引方式也叫做“非聚集”的，之所以這麼稱呼是為了與InnoDB的聚集索引區分。 因為InnoDB的數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含欄位作為主鍵，這個欄位長度為6個位元組，類型為長整形。 不同存儲引擎的索引實現方式對於正確使用和優化索引都非常有幫助，例如知道了InnoDB的索引實現後，就很容易明白為什麼不建議使用過長的欄位作為主鍵，因為所有輔助索引都引用主索引，過長的主索引會令輔助索引變得過大。再例如，用非單調的欄位作為主鍵在InnoDB中不是個好主意，因為InnoDB數據文件本身是一顆B+Tree，非單調的主鍵會造成在插入新記錄時數據文件為了維持B+Tree的特性而頻繁的分裂調整，十分低效，而使用自增欄位作為主鍵則是一個很好的選擇。
