你真的了解跳跃表吗

   <p>最近换了工作，因为工作的需要，也正好自己想好好研究一下Java这门牛逼的语言，看了一下ElasticSearch和Lucene的源码，之前从来没有写过也没有看过Java的东西，所以也算是恶补了一下Java吧，由于是从C程序员开始的，所以对这种带虚拟机的语言总有一些偏见，老觉得内存不好控制，所以一直以来都没有怎么碰过Java，最近静下心来好好看了一下Java和相关的源码，除了感觉语言本身啰嗦了一点，还是不错的，但是有一点比较受不了就是基本上用vi很难做Java开发，要是没有IDE的话，感觉写Java有些蛋疼啊。</p>    <p>接下来一段时间会多聊一聊ElasticSearch和lucene相关的，因为最近也在研究这个，先看了Lucene的底层代码，确实写得简洁明了，后面有机会会好好写写这方面的东西。</p>    <p>好了，不闲扯了，今天想说一说搜索引擎或者数据库中索引（主要是倒排索引）的字典结构，一个好的高效的字典结构直接影响到索引的效果，而索引的构建其实并不是完全追求速度，还有磁盘空间，内存空间等各个因素，所以在一个索引系统中，需要权衡各个关系，找到一种适合你当前业务的数据结构进行存储。这样才能发挥索引最大的能效，一般情况下，对于索引来说（主要是倒排索引）的字典来说，有 <strong>跳跃表，B+树，前缀树，后缀树，自动状态机，哈希表</strong> 这么几种数据结构，其实只要是一个快速的查找型的数据结构就可以用来做索引的字典。</p>    <p>我们从简单的开始，一个一个来说说，今天先说说跳跃表，跳跃表结构非常非常简单，但是，你真的了解它么？</p>    <h2>跳跃表</h2>    <p>跳跃表是一种简单，高效的快速查找结构，实现起来成本最小，并且速度也很快，只需要一个图就可以完美的解释跳跃表的样子，而且对于编程人员来说，要实现一个跳跃表看着图就能实现，以下就是跳跃表的结构图，没有什么难度。</p>    <p><img src="https://simg.open-open.com/show/2c45d5105bc285c8ec9055a4d78054b8.png"></p>    <p>跳跃表有几个特点，这种特点对于某些类型的查询是有相当的效率提升的。</p>    <ul>     <li> <p>它是有序的，跳跃表的特点就是有序的，所以对于一些有序类型的数据，比如整数，日期这种，用跳跃表可以进行范围查找。</p> </li>     <li> <p>在构建跳跃表和查询跳跃的复杂度一致，所以也比较适合于在线的实时索引，可以来一个文档，一边查找就一边知道要如何进行插入操作了。</p> </li>     <li> <p>保存到磁盘和从磁盘载入也比较简单，因为本质上是几个链表，所以保存的时候可以按照数组的方式分别保存几个数组就可以了。</p> </li>    </ul>    <p>在lucene中，跳跃表并没有用来存储字典，而是用来存储docid链，这里后面我们说lucene底层和Elasticsearch的时候再说具体结构吧，这篇我们仅用来讨论用跳跃表存字典的情况。</p>    <p>对于跳跃表，我们看看有一些什么样的优化方式可以让其更加适应一些场景。优化的话，我们一般从 <strong>空间</strong> 和 <strong>时间</strong> 两个方面来考虑一个优化，对于空间的话，又分成 <strong>内存空间</strong> 优化和 <strong>磁盘空间</strong> 优化，当然一般首先考虑内存的优化，对于时间来说，也分成 <strong>构建时间</strong> 和 <strong>查询时间</strong> 两个方面来优化，空间和时间是两个相互矛盾的优化，具体到实际操作上如何取舍就要看具体的场景了。</p>    <h3>空间优化</h3>    <ul>     <li> <p>如果我们的内存空间不够或者说跳跃表存储的序列太长了，那么我们可以把跳跃表的最底层的链表存储在磁盘上，这是一次优化情况，那么检索的时候需要一次到多次磁盘才能检索到数据，相当于用一部分性能来获得更大的数据加载能力。</p> </li>     <li> <p>如果还需要继续优化的话，那么可以把上面几层的节点的数据项变成指针，都指向磁盘的偏移地址上，那么就更加的节省空间了，这样又牺牲了一部分检索性能，因为每一次读取一个节点，不管是不是底层节点，都需要读取一次磁盘来获得数据，对于上面两个优化方式，对应的数据结构的图如下，可以看到这样优化下去，内存的使用量会变得很小了。</p> </li>    </ul>    <p><img src="https://simg.open-open.com/show/7c364f9aeee72236ecdeb3fa52af5ffb.png"></p>    <p>但是上图这种存储方式不适合动态的增加或者删除节点，因为一次这样的更新操作需要操作好几次磁盘，并且会导致磁盘上各个节点是不连续的，非常影响效率，所以比较适合那种写入以后就不会变化的跳跃表的情况。</p>    <h3>时间优化</h3>    <ul>     <li> <p>最简单的时间优化，那就是把数据全部加载到内存，直接查询速度就快起来了，这个没什么难度，当然也可用用LRU这种缓存算法来折中一下，不消耗太大的空间并且也比直接放磁盘要快一些，或者用mmap让操作系统来帮你做这个事情也可以，不过使用LRU或者mmap的话，编程的难度和数据结构的设计难度就会要变难不少，得看你实现出来的成本了。</p> </li>     <li> <p>还有一种方式就是在查找算法上优化一下，用二分查找代替直接遍历，这也只适合静态的情况，需要修改一下数据结构，将每一层的链表变成数组载入到内存中，这样查找的时候可以通过二分快速的定位到节点上。</p> </li>    </ul>    <p><img src="https://simg.open-open.com/show/d91f1970754eaffb277d5d1ed7263d99.png"></p>    <ul>     <li> <p>跳跃表的层级的增加，一般情况下是通过一个概率来计算是否要增加层级节点的，但是对于一些特殊的类型，其实在构建跳跃表的时候是可以特殊处理的，比如跳跃表用来存储时间序列，那么我们其实可以每当时间过去了一分钟或者一小时或者一天就增加一个层级，假设最小的时间维度是秒，如果一分钟和一小时增加层级的话，那么一天的数据就是三层，而且第一层最多24个节点，第二层最多1440个节点，最底层86400个节点，把第一层和第二层完全载入内存的话应该说没有任何压力，甚至为了查询速度，第一层和第二层节点数固定下来，就是24和1440，这样查询的话都不用遍历链表了，直接可以通过运算就能求出下标然后直接跳到最底层上面来了。这是个典型的用了一定的内存空间来交换出更快的查询时间。</p> </li>    </ul>    <p><img src="https://simg.open-open.com/show/5a20c58550023bbd2a173f70383632ae.png"></p>    <p>上图中的底层表示秒，第二层表示分钟，第一层表示小时，那个红色的节点表示那一分钟其实是没数据的，为了把节点数固定下来虚拟出来的节点，这样可以提高查询的效率。</p>    <h3>优化的取舍</h3>    <p>上面两个大类型的优化，其实很多地方是矛盾的，具体取舍的时候就要看你的业务场景了，假设需要用跳跃表来存储你的主键，你的业务场景是更新操作很少，查询操作主要针对其他字段而非主键的话，那么底层存磁盘上，上面几层的数据项也存磁盘上，并且通过LRU或者mmap交换内存和磁盘空间的跳跃表比较适合你。如果用来存储分词后的关键字的话，因为中文分词以后关键词的量级一般在几十万这个级别，那么直接载入内存的话也能接受，所以直接加载到内存的方式可能更适合你。</p>    <p>好了，今天先写这么多，后面还有很多字典结构可以优化的，慢慢来说，正好最近自己也在研究索引的优化，可以留言讨论哈，有说得不对的，随便拍。</p>    <p>如果你觉得不错，欢迎转发给更多人看到，也欢迎关注我的公众号，主要聊聊搜索，推荐，广告技术，还有瞎扯。。文章会在这里首先发出来：）扫描或者搜索微信号XJJ267或者搜索西加加语言就行</p>    <p><img src="https://simg.open-open.com/show/2d1f193af8adc61de7ddf5a8abd0a848.jpg"></p>    <p> </p>