點擊有驚喜

之前對index的了解僅僅是停留在使用上面，一直都不太清楚index的原理沒，那段時間專門看了一下，這里我梳理一下

如果我們想要理解索引的原理，我們首先要了解一種最基本的數據結構Btree 就是balance tree ，這個圖就是多路平衡排序樹的一個例子，我們了解到每個節點的存儲是按key-valuede形式存放的，一般一個節點的大小不會哦超過一個磁盤塊的大小，這很重要，因為這關系到一個非常重要的指標IO次數，
2，多路的，它不是二叉樹，
3，平衡樹，數據有序，右側數據一定會大于等于左側的數據，并且平衡，有利于數據的快速檢索，
4，B樹我們知道它一般非葉子節點都用來存放索引信息，而真正的數據都存放于葉子結點

我們都知道當我們為表插入數據時需要指定對應的Primary Key ，我們都知道的是Id為了唯一區別當前這條數據，很多人不知道的是Id還是構成數據庫表主索引的關鍵字，就是說阿，我一旦創建了表指定PK之后，系統會自動創建一個以ID為關鍵字的構成的以Btree為數據結構的主索引表，那為什么要這樣做呢，原因很簡單，因為最常見的查詢都是根據Id進行的，你可以做在數據量比較大的數據庫表上面做一個實驗，分別根據PK查詢和非索引字段查詢，比較一下時間就看得出來，一般Id的查詢時非常快的。那么通常意義上所說的索引是什么樣的呢。，一旦我們為數據庫表的某一個字段創建index以后，操作系統會為數據庫表生成一個Btree并和數據庫數據一起存儲在Disk上，而且這個Btree的節點的value就是我們選定的那個數據庫表的字段。

上圖解釋了一個簡單的查詢的過程，當程序發起這樣一個查詢時，首先主索引表會被load到內存中去，解析sql語句找到關鍵字value是1256，然后對主索引表開始進行查詢，找到value為1256的節點，然后怎么辦呢，我們還沒有找對1256對應的這條數據在硬盤上的真正位置，沒關系Btree已經為我們想好了，前面說過Btree的真正數據都存放在葉子節點，這里1256對應的節點的子節點就是葉子節點，葉子節點中存放的就是1256這條數據存放在硬盤上的地址，系統找到這個地址后，如果這條數據只是占用了一個磁盤塊大小的空間，那么系統只需要再訪問一次磁盤就可以了，所以之所以Id查詢的速度快的原因就是IO次數很少，其時間復雜度為logn

還有一點我們必須知道的是非主索引（非聚集索引）與主索引的關系的，比如說我們在User表上面的name字段建立了一個索引，那現在User 表有兩個索引表了，如果我們發起了
Select * from user where name=’tom’
這個sql的執行過程我們現在可以看得很清楚，首先name索引表load內存，找到value=‘tom’
的節點，然后進入葉子節點，這里注意非主索引表的葉子節點存放的是這行數據的ID值，這么設計當然是非常合乎情理的，根據葉子節點確定該行數據Id值，然后load主索引表到內存中，根據Id再查找這行數據真正的地址

現在你明白為什么name上沒有索引的時候，查詢超級慢呢，就是因為這種查詢方法是全表掃描，就是從頭到尾一行一行的把數據load到內存中查看name是否匹配，最壞的情況就是把整個表的數據查詢一邊，IO 次數太多了，嚴重影響了查詢的時間。
現在可以確定Btree的使用確實大大提高了查詢速度，我們需要來思考一下為什么偏偏選用了Btree這種我們不是那么熟悉的數據結構來做索引？

1．第一個問題為什么沒有選用Hash structure?
這個疑問應該是很多人都回想到的，因為如果用Hash表來做索引表是什么樣的呢，優點是查詢速度更快了，試想一下是不是，我們可以把每一行數據的地址都記錄在索引表里面阿，查詢的時候只要把hash索引表load內存，在沖突比較少的情況下查一次就可以確定該數據的位置了，時間復雜度是O(1),確實非常快的，熟悉計算機組成原理的同學應該非常清楚 hash索引在cache，虛存以及文件系統的設計中有大量的應用，其最大優勢就是查詢速度快，明顯的空間換時間。 那它的缺點當然也是非常突出的，很簡單如果你的數據庫表數據量非常大那么想當然的索引表也非非常之大，這對于內存的利用率來說還是不好的，Hash 表無法當作數據庫索引還有一個致命缺點就是，它無法進行范圍的查詢，hash函數的映射只是支持單值查詢，如果selct * from use where age>12 這樣的查詢Hash表是無法實現的，當然mongodb支持創建Hash索引，后面我還會講到。
2．為什么沒有選用BST(平衡二叉樹)？
BST 和Btree有很多類似，我們應該更熟悉BST，有序并且平衡，，但是當數據量比較大時，Btree將更加的扁平，高度更低，查詢速度更快

當我們為mongodb插入文檔時，如果不指定_id，mongodb會自動生成id字段作為當前文檔的唯一標識，和mysql是一樣的，也就是說每一個文檔都會有自己唯一的id mongodb會利用id來建立Btree主索引，這是默認建立的

單字段索引，比如我們在person文檔的age字段上建立索引，語句如下，，和之前所講的一樣，利用age字段為索引結點建立age索引表，葉結點存儲主索引的值，查詢過程是，通過age找到對應id，再通過id主索引找對對應的文檔，，這里的參數可以指定索引的排序，1 為升序 -1為降序，
然后我們看復合索引，既是在兩個或是兩個以上的字段建立聯合索引，原理是一樣的，聯合age和name兩個字段組織索引結點生成索引表，葉結點還是指向主索引表，也就是說，不管ji不管jianl不管建立多少索引，查詢時最終還是會指向主索引表去查詢文檔，當然也有例外，比如覆蓋索引我們后面會提到

索引性能的分析

索引的建立對于數據庫性能有什么影響？ 建立索引有沒有什么原則？
我們了解了索引的原理之后知道，查詢的時候，如果查詢條件不依賴PK，如果不建立索引就會引發全表掃描，如果數據量比較大時，全表掃描根本不可行，建立索引可以直接加快檢索速度，IO 也呈指數即下降，那sh那是不是索引建的越多就愈好尼，也不盡然，因為查詢期間索引表需要load到內存中，索引也不是越多越好，數據量比較大時，索引也會占去相當一本分內存，，而且索引應該建立在一些不經常更新并且數據重復量比較少的字段上，如果這個字經常更新，其對應的索引也需要更新，這個消耗比較高，還有就是如果這個字段的數據在數據庫的重復率較高的話，建立索引的意義就沒有那么大了，比如查找age=20的結果非常多，這樣的效率跟全表掃描不相上下，，還有就是有時候復合索引建立，如果我們要在age和name上建立索引，只需建立兩個字段的復合索引，復合索引表中結點是有兩個字段組成，不用單個在兩個字段上都建立索引，便可以實現高效查詢。

OK多說無益為了證明我的觀點正確我還是要做一點實驗的，我會借助mongodb自帶的explain 函數來證明我前面的關鍵

這個查詢是沒有在age字段建立索引之前發起的查詢，explain函數可以監控查詢過程，是一個非常好用的函數，可以看到 “COLLSCAN” 立即明白這個查詢過程是全表掃面，，collection scan
Collection就是mongodb的一個表的單位，ok 然后我建立索引以后，再查一次看看有什么變化

能看出 掃描端倪嗎，我們看內層的stage：INXSCAN index scan 使用了索引掃描，，，外層stage：Fetch 大家應該可以猜得到了，這里應該是去查主索引了沒錯了 。 ok 我覺得索引應該已經講得非常明白了，如果有什么不理解可以再去baidu看看。

點擊有驚喜

總結

以上是生活随笔為你收集整理的mongodb系列02-------深入理解索引原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。