根據(jù)前兩篇的鋪墊,，今天我們可以去具體看看索引的知識了,。索引的知識以mysql為基本,，雖然本人項目使用的PGSql....

B,B+樹的性能考量：

我們知道數(shù)據(jù)庫的文件都是存儲在磁盤中，那么IO操作就是評價一個索引結(jié)構(gòu)好壞的最好標準,。如果這個索引是順序結(jié)構(gòu),，那么查詢一個數(shù)據(jù)的時間復(fù)雜度就是O(N)，數(shù)據(jù)少還行,，到百萬,，千萬級別的時候，查詢一次也要O(N),，就意味著N次IO,，要命。

而B樹則不然,，根據(jù)第一章的學(xué)習(xí),，訪問B樹中最下方的一個節(jié)點數(shù)據(jù)，只發(fā)生了3次IO操作（查找了3個高度的節(jié)點,，最終定位到當前節(jié)點中）,。而更巧妙的地方在于，數(shù)據(jù)庫系統(tǒng)在設(shè)計的時候,，一個節(jié)點的大小就等于一頁的大小（關(guān)于頁的概念,，此文不分析），這就意味著一次IO就能一個節(jié)點完全載入其中,。

1.B樹的時間復(fù)雜度是一個漸進式的O(h)=O(log d(N) ),。h是樹高，d是度,，也就是分支的數(shù)目,，N是總記錄數(shù)。

2.B樹的高度 h=log(m+1)N（不確定,，但是估計關(guān)系差不多是如此）,假設(shè) 數(shù)據(jù)總量是N,，每個節(jié)點的數(shù)據(jù)項是m。由此可知N一定的情況下,，m越大,，h就越小。而m = 節(jié)點的大小/數(shù)據(jù)項的大小,。而節(jié)點的大小剛剛說過,，大小基本就是確定的，因此如果數(shù)據(jù)項空間越小,，則m就越多,，m越多，樹的高度h就越小，查找更有利,。

這也就是索引字段為什么要小的緣故,，小了的話節(jié)點的數(shù)據(jù)項就越多，高度就越小,。而B+樹內(nèi)把真是的數(shù)據(jù)又放在了葉子節(jié)點中,，非葉子節(jié)點中只存放了索引的數(shù)據(jù)，保證了數(shù)據(jù)項盡可能的多,。保證樹的高度,。

Mysql中存儲引擎的索引實現(xiàn)：

Mysql有兩種存儲引擎，MyISAM和InnoDB,，InnoDB常聽說,，好像用的也是最多的，MyISAM不常聽說,。

1.MyISAM使用的是B+樹作為引擎,，下圖展示的是主鍵索引的示意圖：

可以看見索引文件和數(shù)據(jù)記錄其實是分開來的，索引文件里存儲的其實是數(shù)據(jù)記錄的地址,。

2.MyISAM輔助索引和主鍵索引類似,，但是輔助索引的key可以重復(fù)，這是和主鍵不同的地方,。

3.InnoDB的索引實現(xiàn)也是B+樹,，但是具體的方式確不一樣。

3.1第一點,，數(shù)據(jù)文件本身就是索引文件,，這一點怎么理解呢,？還記得B+樹的葉子節(jié)點存儲了具體數(shù)據(jù)嘛,，在InnoDB里，葉子節(jié)點存儲的樹真正的數(shù)據(jù)值,，而不是MyISAM里存儲的是地址,。索引的key就是數(shù)據(jù)表的主鍵。InnoDB主索引的示意圖如下,，可以看見葉節(jié)點包含了完整的數(shù)據(jù)記錄,，這種索引也叫做聚集索引。因為InnoDB的數(shù)據(jù)文件本身要按照主鍵聚集,，所以必須要有主鍵,。如果沒有顯示指定，則Mysql會自動選擇可以唯一標識的數(shù)據(jù)列作為主鍵,，如果不存在這種列,，則Mysql自動為InnoDB生成一個隱含字段，占位6字節(jié)，長整型,。

3.2InnoDB輔助索引也和MyISAM不同,，輔助索引里面存儲的是數(shù)據(jù)的主鍵而不是地址，可以這么說InnoDB的輔助索引最終還是要依賴主鍵索引來實現(xiàn),。下圖是以名字為索引的單列索引B+樹結(jié)構(gòu)：

3.3輔助索引里面有一個比較特殊的索引叫覆蓋索引,。它奇特在哪邊呢？從3.2我們知道輔助索引的data區(qū)域其實存儲的是主鍵的地址,，需要通過主鍵進行再一次定位訪問到具體的數(shù)據(jù),。那么假設(shè)：

select uage,uname from user where uage = 12; 

如果我們建立的是復(fù)合索引(uage,uname)的話，上面一條語句會用到索引,，而且能夠直接返回出ucard和uname,，而不需要再去進行主鍵定位的操作，這就是特別之處,。所以這個復(fù)合索引其實可以說成是一種覆蓋索引,。

那么復(fù)合索引的B+樹結(jié)構(gòu)是怎么樣的呢？這里我們假設(shè)user表結(jié)構(gòu)中的聯(lián)合索引是(age,name,address),。下圖不能確認是否是正確的,，只是通過參考不同的文章總結(jié)出的自己的假設(shè)。

通過這個結(jié)構(gòu)我們可以看見,，在葉子節(jié)點中存儲的數(shù)據(jù)是age,name,address的值（假設(shè)這些數(shù)據(jù)都是按照順序排列好的,，圖中是隨意寫的），那么如果我們只想要這幾個值的話,，都不需要再進行主鍵定位查詢了,，提高了一些效率。

小結(jié)： 

InnoDB的聚集索引是按照主鍵搜索,，是最高效的,，輔助索引需要走兩次索引，首先查詢輔助索引得到主鍵,，再跟進主鍵查詢獲得記錄,。

問題1：不建議主鍵字段過長：原因上面第2點也講過一些，過長會造成數(shù)據(jù)項空間變大,，每個節(jié)點數(shù)據(jù)項數(shù)目變少,，高度增加。

另外我們發(fā)現(xiàn)輔助索引的data域記錄的也是主鍵,，因此簡介造成輔助索引變大,，查詢困難。

問題2：非單調(diào)字段：如果不是單調(diào)字段的話,，會造成B+樹不斷的調(diào)整,，十分低效,，上一篇分析過插入和刪除。使用自增字段的話會保持一個相對穩(wěn)定的順序,。