倒排列表

虽然Elasticsearch是针对搜索场景来定制的，但如前文所言，实际应用中常常用Elasticsearch来作为数据库使用，就是因为倒排列表的特性。可以用比较朴素的观点来理解倒排索引：

对Elasticsearch中的数据进行查询时，本质就是求多个排好序的序列求交集。非数值类型字段涉及到分词问题，大多数内部使用场景下，可以直接使用默认的bi-gram分词：

即将所有Ti和T(i+1)组成一个词（在Elasticsearch中叫 term），然后再编排其倒排列表，这样倒排列表大概就是这样的：

当用户搜索“天气很好”时，其实就是求：天气、气很、很好三组倒排列表的交集。但这里的相等判断逻辑有些特殊，用伪代码表示：

func equal() {
    if postEntry.docID of '天气' == postEntry.docID of '气很' &&
        postEntry.offset + 1 of '天气' == postEntry.offset of '气很' {
            return true
    }

    if postEntry.docID of '气很' == postEntry.docID of '很好' &&
        postEntry.offset + 1 of '气很' == postEntry.offset of '很好' {
        return true
    }

    if postEntry.docID of '天气' == postEntry.docID of '很好' &&
        postEntry.offset + 2 of '天气' == postEntry.offset of '很好' {
        return true
    }

    return false
}

多个有序列表求交集的时间复杂度是 ?(?∗?) ，? 为给定列表中元素数最小的集合，? 为给定列表的个数。

在整个算法中起决定作用的一是最短的倒排列表的长度，其次是词数总和，一般词数不会很大，所以起决定性作用的，一般是所有倒排列表中最短的那一个的长度。

因此，文档总数很多的情况下，搜索词的倒排列表最短的那一个不长时，搜索速度也会很快。如果用关系型数据库，那就需要按照索引来慢慢扫描。