MySQL的MyISAM、InnoDB引擎默認(rèn)均使用B+樹索引（查詢時(shí)都顯示為“BTREE”），本文討論兩個(gè)問題：
創(chuàng)新互聯(lián)公司專注于企業(yè)營銷型網(wǎng)站建設(shè)、網(wǎng)站重做改版、豐南網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5頁面制作、商城建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為豐南等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。為什么索引無法全部裝入內(nèi)存
索引結(jié)構(gòu)的選擇基于這樣一個(gè)性質(zhì)：大數(shù)據(jù)量時(shí)，索引無法全部裝入內(nèi)存。
為什么索引無法全部裝入內(nèi)存？假設(shè)使用樹結(jié)構(gòu)組織索引，簡單估算一下：
假設(shè)索引存儲(chǔ)在內(nèi)存中。也就是說，每在物理盤上保存2G的數(shù)據(jù)，就要占用200MB的內(nèi)存，索引:數(shù)據(jù)的占用比約為1/10。1/10的占用比算不算大呢？物理盤比內(nèi)存廉價(jià)的多，以一臺(tái)內(nèi)存16G硬盤1T的服務(wù)器為例，如果要存滿1T的硬盤，至少需要100G的內(nèi)存，遠(yuǎn)大于16G。
考慮到一個(gè)表上可能有多個(gè)索引、聯(lián)合索引、數(shù)據(jù)行占用更小等情況，實(shí)際的占用比通常大于1/10，某些時(shí)候能達(dá)到1/3。在基于索引的存儲(chǔ)架構(gòu)中，索引:數(shù)據(jù)的占用比過高，因此，索引無法全部裝入內(nèi)存。
其他結(jié)構(gòu)的問題
由于無法裝入內(nèi)存，則必然依賴磁盤（或SSD）存儲(chǔ)。而內(nèi)存的讀寫速度是磁盤的成千上萬倍（與具體實(shí)現(xiàn)有關(guān)），因此，核心問題是“如何減少磁盤讀寫次數(shù)”。
首先不考慮頁表機(jī)制，假設(shè)每次讀、寫都直接穿透到磁盤，那么：
BST、AVL、RBT很好的將讀寫次數(shù)從O(n)優(yōu)化到O(log2(n))；其中，AVL和RBT都比BST多了自平衡的功能，將讀寫次數(shù)降到大O(log2(n))。
假設(shè)使用自增主鍵，則主鍵本身是有序的，樹結(jié)構(gòu)的讀寫次數(shù)能夠優(yōu)化到樹高，樹高越低讀寫次數(shù)越少；自平衡保證了樹結(jié)構(gòu)的穩(wěn)定。如果想進(jìn)一步優(yōu)化，可以引入B樹和B+樹。
B樹解決了什么問題
很多文章將B樹誤稱為B-（減）樹，這可能是對(duì)其英文名“B-Tree”的誤解（更有甚者，將B樹稱為二叉樹或二叉搜索樹）。特別是與B+樹一起講的時(shí)候。想當(dāng)然的認(rèn)為有B+（加）樹就有B-（減）樹，實(shí)際上B+樹的英文名是“B+-Tree”。
如果拋開維護(hù)操作，那么B樹就像一棵“m叉搜索樹”（m是子樹的大個(gè)數(shù)），時(shí)間復(fù)雜度為O(logm(n))。然而，B樹設(shè)計(jì)了一種高效簡單的維護(hù)操作，使B樹的深度維持在約log(ceil(m/2))(n)~logm(n)之間，大大降低樹高。
再次強(qiáng)調(diào)：
不要糾結(jié)于時(shí)間復(fù)雜度，與單純的算法不同，磁盤IO次數(shù)才是更大的影響因素。讀者可以推導(dǎo)看看，B樹與AVL的時(shí)間復(fù)雜度是相同的，但由于B樹的層數(shù)少，磁盤IO次數(shù)少，實(shí)踐中B樹的性能要優(yōu)于AVL等二叉樹。
同二叉搜索樹類似，每個(gè)節(jié)點(diǎn)存儲(chǔ)了多個(gè)key和子樹，子樹與key按順序排列。
頁表的目錄是擴(kuò)展外存+加速磁盤讀寫，一個(gè)頁（Page）通常4K（等于磁盤數(shù)據(jù)塊block的大小，見inode與block的分析），操作系統(tǒng)每次以頁為單位將內(nèi)容從磁盤加載到內(nèi)存（以攤分尋道成本），修改頁后，再擇期將該頁寫回磁盤?？紤]到頁表的良好性質(zhì)，可以使每個(gè)節(jié)點(diǎn)的大小約等于一個(gè)頁（使m非常大），這每次加載的一個(gè)頁就能完整覆蓋一個(gè)節(jié)點(diǎn)，以便選擇下一層子樹；對(duì)子樹同理。對(duì)于頁表來說，AVL（或RBT）相當(dāng)于1個(gè)key+2個(gè)子樹的B樹，由于邏輯上相鄰的節(jié)點(diǎn)，物理上通常不相鄰，因此，讀入一個(gè)4k頁，頁面內(nèi)絕大部分空間都將是無效數(shù)據(jù)。
假設(shè)key、子樹節(jié)點(diǎn)指針均占用4B，則B樹節(jié)點(diǎn)大m * (4 + 4) = 8m B；頁面大小4KB。則m = 4 * 1024 / 8m = 512，一個(gè)512叉的B樹，1000w的數(shù)據(jù)，深度大 log(512/2)(10^7) = 3.02 ~= 4。對(duì)比二叉樹如AVL的深度為log(2)(10^7) = 23.25 ~= 24，相差了5倍以上。震驚！B樹索引深度竟然如此！
另外，B樹對(duì)局部性原理非常友好。如果key比較?。ū热缟厦?B的自增key），則除了頁表的加成，緩存還能進(jìn)一步預(yù)讀加速。美滋滋~
B+樹解決了什么問題
B樹的剩余問題
然而，如果要實(shí)際應(yīng)用到數(shù)據(jù)庫的索引中，B樹還有一些問題：
問題1
數(shù)據(jù)表的記錄有多個(gè)字段，僅僅定位到主鍵是不夠的，還需要定位到數(shù)據(jù)行。有3個(gè)方案解決：
方案1直接pass，存儲(chǔ)數(shù)據(jù)行將減少頁面中的子樹個(gè)數(shù)，m減小樹高增大。
方案2的節(jié)點(diǎn)中增加了一個(gè)字段，假設(shè)是4B的指針，則新的m = 4 * 1024 / 12m = 341.33 ~= 341，深度大 log(341/2)(10^7) = 3.14 ~= 4。
方案3的節(jié)點(diǎn)m與深度不變，但時(shí)間復(fù)雜度變?yōu)榉€(wěn)定的O(logm(n))。
方案3可以考慮。
問題2
實(shí)際業(yè)務(wù)中，范圍查詢的頻率非常高，B樹只能定位到一個(gè)索引位置（可能對(duì)應(yīng)多行），很難處理范圍查詢。改動(dòng)較小的是2個(gè)
方案：
乍一看感覺方案1比方案2好——時(shí)間復(fù)雜度和常數(shù)項(xiàng)都一樣，方案1還不需要改動(dòng)。但是別忘了局部性原理，不管節(jié)點(diǎn)中存儲(chǔ)的是數(shù)據(jù)行還是數(shù)據(jù)行位置，方案2的好處在于，依然可以利用頁表和緩存預(yù)讀下一節(jié)點(diǎn)的信息。而方案1則面臨節(jié)點(diǎn)邏輯相鄰、物理分離的缺點(diǎn)。
引出B+樹
綜上，問題1的方案2與問題2的方案1可整合為一種方案（基于B樹的索引），問題1的方案3與問題2的方案2可整合為一種（基于B+樹的索引）。實(shí)際上，數(shù)據(jù)庫、文件系統(tǒng)有些采用了B樹，有些采用B+樹。
由于某些猴子暫未明白的原因，包括MySQL在內(nèi)的主流數(shù)據(jù)庫多選擇了B+樹。即：
主要變動(dòng)如上所述：
B樹和B+樹的增、刪、查過程
B樹的增刪過程暫時(shí)可參考從B樹、B+樹、B*樹談到R 樹的“6、B樹的插入、刪除操作”小節(jié)，B+樹的增刪同理。此處暫不贅述。
Mysql索引優(yōu)化
根據(jù)B+樹的性質(zhì)，很容易理解各種常見的MySQL索引優(yōu)化思路。
暫不考慮不同引擎之間的區(qū)別。
優(yōu)先使用自增key作為主鍵
前面的分析中，假設(shè)用4B的自增key作為索引，則m可達(dá)到512，層高僅有3。使用自增的key有兩個(gè)好處：
自增key一般為int等整數(shù)型，key比較緊湊，這樣m可以非常大，而且索引占用空間小。最極端的例子，如果使用50B的varchar（包括長度），那么m = 4 * 1024 / 54m = 75.85 ~= 76，深度大 log(76/2)(10^7) = 4.43 ~= 5，再加上cache缺失、字符串比較的成本，時(shí)間成本增加較大。同時(shí)，key由4B增長到50B，整棵索引樹的空間占用增長也是極為恐怖的（如果二級(jí)索引使用主鍵定位數(shù)據(jù)行，則空間增長更加嚴(yán)重）。
自增的性質(zhì)使得新數(shù)據(jù)行的插入請(qǐng)求必然落到索引樹的最右側(cè)，發(fā)生節(jié)點(diǎn)分裂的頻率較低，理想情況下，索引樹可以達(dá)到“滿”的狀態(tài)。索引樹滿，一方面層高更低，一方面刪除節(jié)點(diǎn)時(shí)發(fā)生節(jié)點(diǎn)合并的頻率也較低。
優(yōu)化經(jīng)歷：
猴子曾使用varchar(100)的列做過主鍵，存儲(chǔ)containerId，過了3、4天100G的數(shù)據(jù)庫就滿了，DBA小姐姐郵件里委婉表示了對(duì)我的鄙視。。。之后增加了自增列作為主鍵，containerId作為unique的二級(jí)索引，時(shí)間、空間優(yōu)化效果相當(dāng)顯著。
最左前綴匹配
索引可以簡單如一個(gè)列(a)，也可以復(fù)雜如多個(gè)列(a, b, c, d)，即聯(lián)合索引。如果是聯(lián)合索引，那么key也由多個(gè)列組成，同時(shí)，索引只能用于查找key是否存在（相等），遇到范圍查詢(>、<、between、like左匹配)等就不能進(jìn)一步匹配了，后續(xù)退化為線性查找。因此，列的排列順序決定了可命中索引的列數(shù)。
如有索引(a, b, c, d)，查詢條件a = 1 and b = 2 and c > 3 and d = 4，則會(huì)在每個(gè)節(jié)點(diǎn)依次命中a、b、c，無法命中d。也就是最左前綴匹配原則。
=、in自動(dòng)優(yōu)化順序
不需要考慮=、in等的順序，mysql會(huì)自動(dòng)優(yōu)化這些條件的順序，以匹配盡可能多的索引列。
如有索引(a, b, c, d)，查詢條件c > 3 and b = 2 and a = 1 and d < 4與a = 1 and c > 3 and b = 2 and d < 4等順序都是可以的，MySQL會(huì)自動(dòng)優(yōu)化為a = 1 and b = 2 and c > 3 and d < 4，依次命中a、b、c。
索引列不能參與計(jì)算
有索引列參與計(jì)算的查詢條件對(duì)索引不友好（甚至無法使用索引），如from_unixtime(create_time) = '2014-05-29'。
原因很簡單，如何在節(jié)點(diǎn)中查找到對(duì)應(yīng)key？如果線性掃描，則每次都需要重新計(jì)算，成本太高；如果二分查找，則需要針對(duì)from_unixtime方法確定大小關(guān)系。
因此，索引列不能參與計(jì)算。上述from_unixtime(create_time) = '2014-05-29'語句應(yīng)該寫成create_time = unix_timestamp('2014-05-29')。
能擴(kuò)展就不要新建索引
如果已有索引(a)，想建立索引(a, b)，盡量選擇修改索引(a)為索引(a, b)。
新建索引的成本很容易理解。而基于索引(a)修改為索引(a, b)的話，MySQL可以直接在索引a的B+樹上，經(jīng)過分裂、合并等修改為索引(a, b)。
不需要建立前綴有包含關(guān)系的索引
如果已有索引(a, b)，則不需要再建立索引(a)，但是如果有必要，則仍然需考慮建立索引(b)。
選擇區(qū)分度高的列作索引
很容易理解。如，用性別作索引，那么索引僅能將1000w行數(shù)據(jù)劃分為兩部分（如500w男，500w女），索引幾乎無效。
區(qū)分度的公式是count(distinct
這個(gè)值很難確定，一般需要join的字段要求是0.1以上，即平均1條掃描10條記錄。
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計(jì)公司。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
重慶分公司
重慶分公司
