Python简易搜索引擎原理及实现（三）通配符查询
在上一篇中，我们引入了AND、OR、ANDNOT操作符，支持三种查询方式。
这篇文章中，我们将在倒排索引的基础上，改进我们的字典结构，使用B+树索引来加快检索速度；同时引入轮排索引（Permuterm Index），以支持通配符的模糊查询方式。
之前我们采用的是哈希表实现的查询功能。
实现dictionary的方法主要有哈希表和搜索树（二叉树、B树、AVL树）；
实现哈希表的dictionary的优点：
（1）查询效率O（1）；
缺点：
（1）哈希冲突。
（2）不支持模糊查询。
（3）哈希函数需要不断变化以适应需求。
实现搜索树的dictionary的优点：
（1）支持模糊查询。
缺点：
（1）查询效率相对较慢。
（2）树要保持平衡。
单个通配符查询
1.尾通配符查询
比如abc*，即通配符出现在尾部的查询就是尾通配符查询，这种查询使用搜索树可以完成，方法就是以a，b，c的顺序遍历树。如下图所示：
如果要查询ab*，则
（1）比较根节点：因为a在a-m中，所以往左走。
（2）因为ab在a-hu之间，因此往左走。
（3）剩下的子节点就是满足要求的结果，遍历并取得他们的posting即可。
2.头通配符查询
如果要进行头通配符查询，则需要引入反向B tree的概念。反向B tree是把B tree查询的顺序反过来。比如要查询*cba，则查询顺序为a,b,c，举例：
查询*ba的步骤：
（1）比较根节点，因为a在a-m之间，则往左走。
（2）因为ba在aa-uh之间，因此往左走。
因此下面的子节点就是满足条件的结果
3.一般通配符查询
比如abccba，只需要分解成abc和cba，并分别运用1，2的知识即可。*但要注意查询出的结果必须在abc*cba中过滤一遍*。因为比如abcba满足abc和cba,但是却不满足abccba；
Why B+ Tree？
可以先看看以下的基本概念，图文并茂讲得还挺清晰的~
B+Tree的特点：
- 每个父节点的元素都出现在子节点中，是子节点的最大（最小）值；
- 根节点的最大元素等同于整棵树的最大元素，后续无论插入多少元素，要始终保持最大元素在根节点上；
- 叶子节点包含了全部元素信息，都带有指向下一个节点的指针，形成有序链表；
- 卫星数据：索引元素所指向的数据记录，比如数据库中的某一行，在B-Tree中每个节点都有，在B+Tree中，只有叶子节点有卫星数据，中间仅仅是索引。
因此，B-Tree适用于文件系统，部分数据库索引（MongoDB，非关系型数据库）
B+Tree用于大部分关系型数据库
B+Tree相比B-Tree的一些优点：
①B+中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多元素，在数据量相同的情况下，B+更加矮胖，因此查询时 I/O次数更少
②B- 范围查询是自顶向下中序遍历，B+只需要在链表做遍历，范围查询更加简便
③B+必须查询到叶子节点，而B-只需找到匹配元素，因此B-查找性能并不稳定（最好是只查到根，最坏是到叶子节点），B+查询更稳定
通配符查询原理
比如查询语句 mon*：找出所有以mon开头的单词。如果采用B+树结构的词典，我们可以很容易的解决，只需要查询范围在mon ≤ w < moo的所有单词就ok了。
但是查询语句 *mon：找出所有以mon结尾的单词就比较困难了。其中一种办法就是我们增加一个额外的B+树来存储所有单词，以从后向前的顺序，然后在这个树上查询范围在nom ≤ w < non的所有单词。
可是如何处理通配符在单词中间的查询呢？
比如query是co*tion的话。我们当然可以分别在B+树查询到co*和*tion的所有单词然后合并这些单词，但是这样开销太大了。
解决办法就是：轮排索引（Permuterm Index），我们把query的通配符转换到结尾处。
设置一个标志$表示单词的结尾。
以hello举例，hello可以被转换成hello$, ello$h, llo$he, lo$hel, o$hell。$代表中hello的结束。现在，查询X等于查询X$，查询XY等于查询Y$X。对于hel*o来说，X等于hel，Y等于o。
既然我们已经把通配符都弄到了单词尾部，现在我们又可以通过B+树像以前那样查询了。
轮排索引的缺点在于，据统计，会使得词典的大小约变为原始的四倍
具体实现思路
对于每个item项，将它的term值取出，用上面提到的轮排的方式，把该item项对应的所有字符串存为B+树的key，item项存为value，即原本的一个item项此时会对应有轮排出的多个key值。 举个例子来说，一个item项的term值是【互联网】，根据上述轮排的定义，它将对应于 互联网$、联网$互、网$互联 这三个字符串，将每个字符串和item当做一组key、value存入B+树结构中。
构建好B+树和轮排索引结构后，就是对搜索词的查询了。
根据上述在轮排原理处提到的多种不同的含通配符的搜索词格式，我们用不同的映射方式，将用户输入的搜索词映射为实际在B+树中查询的搜索词，然后直接到B+树中进行范围搜索即可
测试结果：
