你真的了解跳躍表嗎

最近換了工作，因為工作的需要，也正好自己想好好研究一下Java這門牛逼的語言，看了一下ElasticSearch和Lucene的源碼，之前從來沒有寫過也沒有看過Java的東西，所以也算是惡補了一下Java吧，由于是從C程序員開始的，所以對這種帶虛擬機的語言總有一些偏見，老覺得內存不好控制，所以一直以來都沒有怎么碰過Java，最近靜下心來好好看了一下Java和相關的源碼，除了感覺語言本身啰嗦了一點，還是不錯的，但是有一點比較受不了就是基本上用vi很難做Java開發，要是沒有IDE的話，感覺寫Java有些蛋疼啊。

接下來一段時間會多聊一聊ElasticSearch和lucene相關的，因為最近也在研究這個，先看了Lucene的底層代碼，確實寫得簡潔明了，后面有機會會好好寫寫這方面的東西。

好了，不閑扯了，今天想說一說搜索引擎或者數據庫中索引（主要是倒排索引）的字典結構，一個好的高效的字典結構直接影響到索引的效果，而索引的構建其實并不是完全追求速度，還有磁盤空間，內存空間等各個因素，所以在一個索引系統中，需要權衡各個關系，找到一種適合你當前業務的數據結構進行存儲。這樣才能發揮索引最大的能效，一般情況下，對于索引來說（主要是倒排索引）的字典來說，有 跳躍表，B+樹，前綴樹，后綴樹，自動狀態機，哈希表 這么幾種數據結構，其實只要是一個快速的查找型的數據結構就可以用來做索引的字典。

我們從簡單的開始，一個一個來說說，今天先說說跳躍表，跳躍表結構非常非常簡單，但是，你真的了解它么？

跳躍表

跳躍表是一種簡單，高效的快速查找結構，實現起來成本最小，并且速度也很快，只需要一個圖就可以完美的解釋跳躍表的樣子，而且對于編程人員來說，要實現一個跳躍表看著圖就能實現，以下就是跳躍表的結構圖，沒有什么難度。

跳躍表有幾個特點，這種特點對于某些類型的查詢是有相當的效率提升的。

• 它是有序的，跳躍表的特點就是有序的，所以對于一些有序類型的數據，比如整數，日期這種，用跳躍表可以進行范圍查找。

• 在構建跳躍表和查詢跳躍的復雜度一致，所以也比較適合于在線的實時索引，可以來一個文檔，一邊查找就一邊知道要如何進行插入操作了。

• 保存到磁盤和從磁盤載入也比較簡單，因為本質上是幾個鏈表，所以保存的時候可以按照數組的方式分別保存幾個數組就可以了。

在lucene中，跳躍表并沒有用來存儲字典，而是用來存儲docid鏈，這里后面我們說lucene底層和Elasticsearch的時候再說具體結構吧，這篇我們僅用來討論用跳躍表存字典的情況。

對于跳躍表，我們看看有一些什么樣的優化方式可以讓其更加適應一些場景。優化的話，我們一般從 空間 和 時間 兩個方面來考慮一個優化，對于空間的話，又分成 內存空間 優化和 磁盤空間 優化，當然一般首先考慮內存的優化，對于時間來說，也分成 構建時間 和 查詢時間 兩個方面來優化，空間和時間是兩個相互矛盾的優化，具體到實際操作上如何取舍就要看具體的場景了。

空間優化

• 如果我們的內存空間不夠或者說跳躍表存儲的序列太長了，那么我們可以把跳躍表的最底層的鏈表存儲在磁盤上，這是一次優化情況，那么檢索的時候需要一次到多次磁盤才能檢索到數據，相當于用一部分性能來獲得更大的數據加載能力。

• 如果還需要繼續優化的話，那么可以把上面幾層的節點的數據項變成指針，都指向磁盤的偏移地址上，那么就更加的節省空間了，這樣又犧牲了一部分檢索性能，因為每一次讀取一個節點，不管是不是底層節點，都需要讀取一次磁盤來獲得數據，對于上面兩個優化方式，對應的數據結構的圖如下，可以看到這樣優化下去，內存的使用量會變得很小了。

但是上圖這種存儲方式不適合動態的增加或者刪除節點，因為一次這樣的更新操作需要操作好幾次磁盤，并且會導致磁盤上各個節點是不連續的，非常影響效率，所以比較適合那種寫入以后就不會變化的跳躍表的情況。

時間優化

• 最簡單的時間優化，那就是把數據全部加載到內存，直接查詢速度就快起來了，這個沒什么難度，當然也可用用LRU這種緩存算法來折中一下，不消耗太大的空間并且也比直接放磁盤要快一些，或者用mmap讓操作系統來幫你做這個事情也可以，不過使用LRU或者mmap的話，編程的難度和數據結構的設計難度就會要變難不少，得看你實現出來的成本了。

• 還有一種方式就是在查找算法上優化一下，用二分查找代替直接遍歷，這也只適合靜態的情況，需要修改一下數據結構，將每一層的鏈表變成數組載入到內存中，這樣查找的時候可以通過二分快速的定位到節點上。

• 跳躍表的層級的增加，一般情況下是通過一個概率來計算是否要增加層級節點的，但是對于一些特殊的類型，其實在構建跳躍表的時候是可以特殊處理的，比如跳躍表用來存儲時間序列，那么我們其實可以每當時間過去了一分鐘或者一小時或者一天就增加一個層級，假設最小的時間維度是秒，如果一分鐘和一小時增加層級的話，那么一天的數據就是三層，而且第一層最多24個節點，第二層最多1440個節點，最底層86400個節點，把第一層和第二層完全載入內存的話應該說沒有任何壓力，甚至為了查詢速度，第一層和第二層節點數固定下來，就是24和1440，這樣查詢的話都不用遍歷鏈表了，直接可以通過運算就能求出下標然后直接跳到最底層上面來了。這是個典型的用了一定的內存空間來交換出更快的查詢時間。

上圖中的底層表示秒，第二層表示分鐘，第一層表示小時，那個紅色的節點表示那一分鐘其實是沒數據的，為了把節點數固定下來虛擬出來的節點，這樣可以提高查詢的效率。

優化的取舍

上面兩個大類型的優化，其實很多地方是矛盾的，具體取舍的時候就要看你的業務場景了，假設需要用跳躍表來存儲你的主鍵，你的業務場景是更新操作很少，查詢操作主要針對其他字段而非主鍵的話，那么底層存磁盤上，上面幾層的數據項也存磁盤上，并且通過LRU或者mmap交換內存和磁盤空間的跳躍表比較適合你。如果用來存儲分詞后的關鍵字的話，因為中文分詞以后關鍵詞的量級一般在幾十萬這個級別，那么直接載入內存的話也能接受，所以直接加載到內存的方式可能更適合你。

好了，今天先寫這么多，后面還有很多字典結構可以優化的，慢慢來說，正好最近自己也在研究索引的優化，可以留言討論哈，有說得不對的，隨便拍。

如果你覺得不錯，歡迎轉發給更多人看到，也歡迎關注我的公眾號，主要聊聊搜索，推薦，廣告技術，還有瞎扯。。文章會在這里首先發出來：）掃描或者搜索微信號XJJ267或者搜索西加加語言就行