為什么 MYSQL 使用 B+樹作為 InnoDB 引擎的索引結構？

　　<Mysql為什么使用B+樹做索引>一文從兩個方面介紹了Mysql為什么選擇B+Tree作為InnoDB引擎索引的數據結構，本文再做一下簡單的總結。

　　Mysql數據庫的數據被分割為多個頁以文件形式儲存在硬盤上的。因此我們每次進行數據庫查詢其實是在進行磁盤 IO，而磁盤 IO 是時間開銷較大的操作！數據庫在進行索引查找的時候每次訪問一個頁都是一次磁盤 IO。因此我們需要選擇一種能夠盡量少做磁盤 IO 的數據結構來構建索引。

　　MySQL 默認的存儲引擎選擇 B+ 樹而不是 B 樹的原因：

　　B 樹能夠在非葉節點中存儲數據，但是這也導致在查詢連續數據時可能會帶來更多的隨機 I/O；而 B+ 樹的所有葉節點可以通過指針相互連接，能夠減少順序遍歷時產生的額外隨機 I/O。B+ 樹的扇出率較大，樹高較小，因而在進行索引搜索的時候需要進行的 IO 也較其他樹的少。B+ 樹只有葉節點會存儲數據，將樹中的每一個葉節點通過指針連接起來就能實現順序遍歷，而遍歷數據在關系型數據庫中非常常見，所以這么選擇是完全沒有問題的。　

為什么 Redis 使用跳表　

　　跳表

　　跳表是一種采用了用空間換時間思想的數據結構。它會隨機地將一些節點提升到更高的層次，以創建一種逐層的數據結構，以提高操作的速度。在理論上能夠在 O(log(n))時間內完成查找、插入、刪除操作。跳表是Redis ZSET類型實現的一種重要數據結構。

　 跳表的性質

　　(1) 由很多層結構組成，level 是通過一定的概率隨機產生的。

　　(2) 每一層都是一個有序的鏈表，默認是升序，也可以根據創建映射時所提供的 Comparator 進行排序，具體取決于使用的構造方法。

　　(3) 最底層(Level 1)的鏈表包含所有元素。

 　  (4) 如果一個元素出現在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會出現。

　　(5) 每個節點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素

 　跳表的優勢

　（1）跳表比 B 樹/B+樹占用的內存更少

  （2）以鏈表的形式遍歷跳躍表，跳躍表的緩存局部性與其他類型的平衡樹相當

  （3）跳表更容易實現、調試等

 思考

　　對并發和性能有要求的情況下，如何選擇合適的數據結構？

　　如果單純比較性能，跳躍表和紅黑樹可以說相差不大，但是加上并發的環境就不一樣了。如果要更新數據，跳躍表需要更新的部分就比較少，鎖的東西也就比較少，所以不同線程爭鎖的代價就相對少了。而紅黑樹有個平衡的過程，牽涉到大量的節點，爭鎖的代價也就相對較高了。性能也就不如前者了。在并發環境下跳表有另外一個優勢，紅黑樹在插入和刪除的時候可能需要做一些平衡操作，這樣的操作可能會涉及到整個樹的其他部分，而跳表的操作顯然更加局部性一些，鎖需要盯住的節點更少，因此在這樣的情況下性能好一些。