| 數據結構 | 實現原理 | key查詢方式 | 查找效率 | 存儲大小 | 插入、刪除效率 |
|---|---|---|---|---|---|
| Hash | 哈希表 | 支持單key | 接近O(1) | 小，除了數據沒有額外的存儲 | O(1) |
| B+樹 | 平衡二叉樹擴展而來 | 單key,范圍，分頁 | O(Log(n) | 除了數據，還多了左右指針，以及葉子節點指針 | O(Log(n)，需要調整樹的結構，算法比較復雜 |
| 跳表 | 有序鏈表擴展而來 | 單key，分頁 | O(Log(n) | 除了數據，還多了指針，但是每個節點的指針小于2,所以比B+樹占用空間小 | O(Log(n)，只用處理鏈表，算法比較簡單 |
對LSM結構感興趣的可以看下cassandra vs mongo (1)存儲引擎
cassandra vs mongo (1)存儲引擎
概括
存儲引擎：
B-Tree
緩存管理
緩存管理的核心在于置換算法，置換算法常見的有FIFO（First In First Out），LRU(Least Recently Used)。關系型數據庫在LRU的基礎上，進行了改進，主要使用LIRS(Low Inter-reference Recency Set)
將緩存分為兩級，第一次采用LRU，最近被使用到的數據會進第一級，如果數據在較短時間內被訪問了兩次或以上，則成為熱點數據，進入第二級。避免了進行全表掃描的時候，可能會將緩存中的大量熱點數據替換掉。
LSM
Log-Structured Merge Tree:結構化合并樹，核心思想就是不將數據立即從內存中寫入到磁盤，而是先保存在內存中，積累了一定量后再刷到磁盤中
LSM VS B-Tree
LSM在B-Tree的基礎上為了獲取更好的寫性能而犧牲了部分的讀性能，同時利用其它的實現來彌補讀性能，比如boom-filter.
1.寫
B樹的寫入，是首先找到對應的塊位置，然后將新數據插入。隨著寫入越來越多，為了維護B樹結構，節點得分裂。這樣插入數據的隨機寫概率就會增大，性能會減弱。
LSM 則是在內存中形成小的排好序的樹，然后flush到磁盤的時候不斷的做merge.因為寫入都是內存寫，不寫磁盤，所以寫會很高效。
2.讀
B樹從根節點開始二分查詢直到葉子節點，每次讀取一個節點，如果對應的頁面不在內存中，則讀取磁盤，緩存數據。
LSM樹整個結構不是有序的，所以不知道數據在什么地方，需要從每個小的有序結構中做二分查詢，找到了就返回，找不到就繼續找下一個有序結構。所以說LSM犧牲了讀性能。但是LSM之所以能夠作為大規模數據存儲系統在于讀性能可以通過其他方式來提高，比如讀取性能更多的依賴于內存/緩存命中率而不是磁盤讀取。
Cassandra
Cassandra是一個寫性能優于讀性能的NoSql數據庫，寫性能好一個原因在于選擇了LSM存儲引擎。
Mongo
MMAPv1
Mongo 3.2以前默認使用MMAPv1存儲引擎，是基于B-Tree類型的。
邊界(padding)
MMAPv1 存儲引擎使用一個叫做”記錄分配”的過程來為document存儲分配磁盤空間。MongoDB與Cassandra不同的是，需要去更新原有的document。如果原有的document空間不足，則需要將這個document移動到新的位置，更新對應的index。這樣就會導致一些不必要的更新，和數據碎片。
為了避免出現上述情況，就有了邊界的概念，就是為document預分配空間。但是這樣就有可能造成資源的浪費。mongo 按照64M,128M,256M…2G的2的冥次方遞增策略預分配，最大2G。在數據量小的情況下問題并不明顯，但是當達到2G時，磁盤占用量大的問題就出來了。
同樣這一點和關系型數據庫也不一樣，關系型數據庫對于長記錄數據會分開存儲。
鎖
MMAPv1使用collection級別的鎖，即一個collecion增，刪，改一次只能有一個。在并發操作時，就會造成等待。
WiredTiger
3.2及其以后的默認存儲引擎,同樣是基于B-Tree的。采用了lock-free,風險指針等并發技術，使得在多核機器上工作的更好。
鎖級別為document。并且引入了compression，減少了磁盤占用。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。
標簽：黔西 梅河口 駐馬店 北京 昌都 鄂爾多斯 荊門 陜西
巨人網絡通訊聲明：本文標題《簡單談談Mysql索引與redis跳表》，本文關鍵詞 簡單,談談,Mysql,索引,與,；如發現本文內容存在版權問題，煩請提供相關信息告之我們，我們將及時溝通與處理。本站內容系統采集于網絡，涉及言論、版權與本站無關。
