多路查找樹——相比于常用的二叉樹延刘，多路查找樹每個節(jié)點(diǎn)可以存儲多個元素和多個孩子指針茫多。主要用于做索引呵晨，來降低程序?qū)ν獯娲疟P設(shè)備上的數(shù)據(jù)的訪問次數(shù)奇钞。
- 【2-3樹】
樹中每個結(jié)點(diǎn)要么是2結(jié)點(diǎn)（即1個元素和2孩子指針或2NULL）澡为，要么是3結(jié)點(diǎn)（即2個元素和3個孩子指針或3NULL）。
- 【2-3-4樹】
2-3樹的擴(kuò)展景埃，增加了4結(jié)點(diǎn)的使用媒至。樹中每個結(jié)點(diǎn)要么是2結(jié)點(diǎn)（即1個元素和2孩子指針或2NULL）顶别，要么是3結(jié)點(diǎn)（即2個元素和3個孩子指針或3NULL），要么是4結(jié)點(diǎn)（即3個元素和4個孩子指針或4NULL）拒啰。 - 都要保證所有的葉子節(jié)點(diǎn)都在同一層次上驯绎，即保證平衡。因此每次插入和刪除結(jié)點(diǎn)后谋旦，都可能要對葉子節(jié)點(diǎn)進(jìn)行調(diào)整条篷。
B樹
B樹結(jié)構(gòu)做索引怎么就能降低程序?qū)ν獯娲疟P設(shè)備上的數(shù)據(jù)的訪問次數(shù)呢？
B+樹——對B樹的改進(jìn)蛤织，使得更適用于文件系統(tǒng)和數(shù)據(jù)庫。
【B樹示例】
【B+樹示例】
- 可以看到鸿染，B+樹的每個分支結(jié)點(diǎn)中只保存了索引值指蚜，而沒有保存實(shí)際的數(shù)據(jù)值。這就使得每個結(jié)點(diǎn)（內(nèi)存頁面）可以存放更多個索引元素涨椒，進(jìn)一步降低了樹的高度摊鸡，提高了查詢的效率。
- 對于B樹在遍歷所有元素時有重復(fù)的缺陷蚕冬，B+樹只要從葉子節(jié)點(diǎn)從左往右遍歷一遍就可以免猾，不會發(fā)生重復(fù)。
B+樹作為數(shù)據(jù)庫索引的實(shí)例囤热，其中0x56等為數(shù)據(jù)實(shí)際地址
為第一列數(shù)據(jù)做索引
為第二列數(shù)據(jù)做索引
數(shù)據(jù)庫索引優(yōu)化策略
高效使用索引的首要條件是知道什么樣的查詢會使用到索引猎提，即查詢語句要滿足B+Tree中的“最左前綴原理”時，才會使用到已經(jīng)創(chuàng)建的索引旁蔼。
既然索引可以加快查詢速度锨苏，那么是不是只要是查詢語句需要，就建上索引棺聊？答案是否定的伞租。因?yàn)樗饕m然加快了查詢速度，但索引也是有代價的：索引文件本身要消耗存儲空間限佩，同時索引會加重插入葵诈、刪除和修改記錄時的負(fù)擔(dān)，另外祟同，MySQL在運(yùn)行時也要消耗資源維護(hù)索引作喘，因此索引并不是越多越好。一般兩種情況下不建議建索引耐亏。
第一種情況是表記錄比較少徊都。
第二種不建議建索引的情況是索引的選擇性較低。所謂索引的選擇性（Selectivity）广辰，是指不重復(fù)的索引值與表記錄數(shù)的比值暇矫。越接近于1說明索引值唯一性越好主之，這對于B+樹的維護(hù)和查詢效率都很好。有一種與索引選擇性有關(guān)的索引優(yōu)化策略叫做
前綴索引李根，就是用列的前綴代替整個列作為索引key槽奕，當(dāng)前綴長度合適時，可以做到既使得前綴索引的選擇性接近全列索引房轿，同時因?yàn)?code>索引key變短而減少了索引文件的大小和維護(hù)開銷粤攒。
詳細(xì)的MySQL數(shù)據(jù)庫索引原理和優(yōu)化看這篇博文：http://blog.codinglabs.org/articles/theory-of-mysql-index.html
