SQlite源码分析

索引的组织结构

在全文检索中，我们需要先知道索引里面存的是什么？在此之前，有必要先来分析一下，顺序扫描速度慢的真正原因。先从用户的角度来考虑，用户提出的查询请求实际上可以认为用户想说的是那写文字中有我要找的字符串，从映射的角度来说，用户的查询请求可以认为是从字符串到文件的一个映射，而对于非结构化内容的文件来说，他能告诉的是，我的文件内容中有没有包含用户要查询的字符串，文件知道的和用户查询的刚好回一个相反的映射关系这样的一个反向关系是顺序扫描慢的一个原因。

索引解决的实际上就是将两者的关系同步的问题，由于用于的查询请求是无法改变映射方向的，那么索引实际上解决的是将文件的映射关系反转，所以索引又被称为反向索引。

左边的字符串列表称为词典。在每个字符串后面有一个由文档编号所构成的单链表，在这个单链表中的文档，表示该文档包含左侧对应词典中的单词。这个单链表又称为倒排表。正因为有这样的索引结构，它保证了用户信息的映射关系和文档映射关系一致。

这个时候如果用户要查找及包含“孙”也包含“赵”的文档，（1）在索引中查找到字符串“孙”，并取出它所对应的倒排表

（2）在索引中查找到字符串“赵”，并取出它所对应的倒排表

（3）合并以上的两个倒排表，也就是找出两个链表中相同编号的文档集合，这样最终的文档集合就是既包含了“孙”又包含了“赵”了。