开发者学堂课程【Lucene知识精讲与实战（下）：Lucene底层关键字数据结构(跳跃表)】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/701/detail/12351
Lucene底层关键字数据结构(跳跃表)
内容介绍：
一、词典数据结构对比
二、跳跃表原理
一、词典数据结构对比
1、索引由关键字，文档号以及词在文档中出现在的位置组成。查询时先查询关键字，根据关键字找到对应的文档号，根据文档号找出文档，在文档中词在哪个位置出现，通过出现的位置直接定位词，速度很快。
2、由于关键字的存储结构不同，造成在查询时查询效率也不一样，不是关键字长度比较小，一本字典加上英文牛津词典的长度，每一次请求，每一次查询都要一个一个的查，顺序扫描法，是数据库中模糊查询使用算法，查询效率比较慢，如果按照某一种特殊结构存储关键字，查的时候可以提高查询关键字的效率，可以进一步优化查询速度。
3、在词典的构建就是关键词存储的结构，如何查询。
4、词典数据结构对比
倒排索引中的词典位于内存，其结构尤为重要,有很多种词典结构，各有各的优缺点，最简单如排序数组,通过二分查找来检索数据，更快的有哈希表，磁盘查找有B树、B+树, 但一个能支持TB级数据的倒排索引结构需要在时间和空间上有个平衡，列了一些常见词典的优缺点:
数据结构 |
优缺点 |
跳跃表简称跳表 |
占用内存小，且可调，但是对模糊查询支持不好 |
排序列表Array/List |
使用二分法查找，不平衡 |
字典树 |
查询效率跟字符串长度有关，但只适合英文词典 |
哈希表 |
性能高，内存消耗大，几乎是原始数据的三倍 |
双数组字典树 |
适合做中文词典，内存占用小，很多分词工具均采用此种算法 |
Finite State Transducers (FST)状态机 |
一种有限状态转移机，Lucene 4有开源实现，并大量使用 |
B树 |
磁盘索引，更新方便，但检索速度慢，多用于数据库 |
Lucene3.0 之前使用的也是跳跃表结构,后换成了 FST ,但跳跃表在 Lucene 其他地方还有应用如倒排表合并和文档号索引。fst 算法更快，省内存。
二、跳跃表原理
1、Lucene3.0 版本之前使用的跳跃表结构后换成了 FST 结构。
2、优点:结构简单、跳跃间隔、级数可控，Lucene3.0 之前使用的也是跳跃表结构，但跳跃表在 Lucene 其他地方还有应用如倒排表合并和文档号索引。用跳表存储关键字，查询时比较快，比顺序扫描法一个字一个字查要快的多。
3、缺点:模糊查询支持不好。
4、单链表:
举例:查找85这个节点,需要查找7次。
表示存的一些数据，关键字。右箭头代表有顺序，如果要查询85，就需要从7开始顺序的查，一个一个的查，存储结构是单链表。
假如查询字典里面的关键词，查询索引中的关键词速度是比较慢的单链表中查询一个元素即使是有序的，我们也不能通过二分查找法的方式缩减查询时间。通俗的讲也就是按照链表顺序一个一个找。
5、跳跃表就是在单链表的基础上进行优化。
跳跃表:
举例:查询85这个节点，一共需要查询6次，分三层。数字跟单链表中数字一样。第一层代表单链表。把单链表的数据随机挑出几个组成第二层，再从第二层中随机挑选几个组成第三层，也可以有第四层第五层。
（1）在 level3 层,查询3次,查询到1结尾,退回到37节点。查询必须是有顺序的。
（2）在 level2 层,从37节点开始查询,查询2次,查询到1结尾，退回到71节点。
（3）在 level1 层,从71节点开始查询,查询1次,查询到85节点。
比单链表只节省一次的查询时间，只能说明跳跃表中数据量不够大，不够长，如果够长，数据量足够大，查询效率要比单链表快很多，数据越大，查询效率快慢比单链表更明显。
