掌握summary索引:从文本挖掘到信息提取的进阶之旅

01 简介

阿里开源havenask搜索引擎包括倒排索引、正排索引和summary索引(也即摘要索引)，summary索引的主要作用是根据文档id获取文档的详细信息，比如每个字段的值

summary索引的构建和查询，底层基于radix tree实现，所以先讲解一下radix tree

02 radix tree

基数树（RadixTree）也称为基数树或者字典树，是一种用于快速存储和检索键值对的数据结构。它是一种树形结构，其中每个节点都包含一个字符或者一个字符序列，而且每个节点都有零个或多个子节点。Radix Tree的主要优点是可以在O(k)的时间复杂度内完成插入、删除和查找操作，其中k是键的长度。与其他树形结构相比，Radix Tree可以更有效地利用内存，因为它可以共享相同的前缀。Radix Tree在许多应用程序中都有广泛的应用，例如Linux内核中的文件系统和网络路由器中的IP路由表。

插入值

对于一颗空树的初始状态，基数树和字典树是一致的，只有 root 节点

对基数树和字典树插入相同的字符串【abcd】，因为新子串无额外分叉，因此可以对子串压缩

对基数树和字典树插入相同的字符串【abce】，当基数树的某一个节点需要分叉时，则对该节点进行分裂后再加入新节点

对基数树和字典树插入相同的字符串【aecb】

对基数树和字典树插入相同的字符串【aecd】

如上图的结果，基数树在这组 case 中，比字典树的深度少 1。以牺牲建树过程中的额外引入分裂操作，来优化查找时的效率

删除值

基于上文中的树，对基数树和字典树删除相同的字符串【abcd】，可以看到因为节点(bc)的分叉消失，因此和子节点合并为(bce)

对基数树和字典树删除相同的字符串【abce】，同理，节点(a)和其子节点(ec)合并为(aec)

对基数树和字典树删除相同的字符串【aecb】

对基数树和字典树删除相同的字符串【aecd】后，两树为空

查询值

因为基数树的本质依然属于字典树，因此在查找使用上和字典树并无不同，只是因为基数树通过压缩，使得在前缀有一定规律的串在树中的深度更低，因此查找效率也较高

03 Linux页缓存应用

Linux 的基数树实现在 lib/radix-tree.c 中，和上文提到的不同，Linux 并不是对一个字符串进行存储，而是一个无符号长整型名为 index 的值，可以从树操作的 Api 中看出：

// 插入值
int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
// 删除值
void *radix_tree_delete(struct radix_tree_root *tree, unsigned long key);

Linux 的 radix tree 是围绕下面三个参数展开的：

• RADIX_TREE_MAP_SHIFT 定义基数，内核通过CONFIG选项，可设置为 4 或 6，默认为 6；
• RADIX_TREE_MAP_SIZE 该数值定义指针数组 slot 的容量；
• RADIX_TREE_MAP_MASK 使用移位与掩码操作实现位组提取；

基数树的核心在于通过压缩控制树的深度，对于整形 index 来说，压缩的内容便是 bit 前缀。使用固定步长对 bit 进行右移时，可以获得确定长度的前缀。

int16(100)  // shift=12 treeLevel=0 val=0000
int16(1000) // shift=12 treeLevel=0 val=0000
int16(100)  // shift=6  treeLevel=1 val=0000000001
int16(1000) // shift=6  treeLevel=1 val=0000001111
int16(100)  // shift=0  treeLevel=2 val=0000000001100100
int16(1000) // shift=0  treeLevel=2 val=0000001111101000

如果每次右移一个固定步长后，树的深度加一，则树的深度也是固定的（比特位数/步长）。Linux 默认值为 6是 bit 位的步长，其含义是每右移 6 个 bit 为一个单位，因此对于上面的数字，可以建树为：

RADIX_TREE_MAP_SIZE 和 RADIX_TREE_MAP_MASK 本质是在实现 hash 桶操作，前者定义了桶的大小，而后者进行 hash 运算（就是取余）。对 index 右移之后，可以通过 hash 桶操作，获取确定的子节点。

最简单的 hash 操作便是取余，RADIX_TREE_MAP_MASK 是一个小技巧，如下的两种写法是等效的：

(index >> shift) % RADIX_TREE_MAP_SIZE
(index >> shift) & RADIX_TREE_MAP_MASK

对于一个 index，可以通过如下 hash 计算，获取下一个节点：

slot := index >> currentNode.shift & RADIX_TREE_MAP_MASK
currentNode = currentNode.slots[slot]

最后，通过如下 int16 的若干 index 建树举例：

int16(60)     // 二进制表示：0000000000111100
int16(1000)   // 二进制表示：0000001111101000
int16(10000)  // 二进制表示：0010011100010000
int16(55520)  // 二进制表示：1101100011100000
int16(65001)  // 二进制表示：1111110111101001

可以建树为：

以 index=1000 举例注释：

1. 1000 >>12% 64 == 0 在slots[0]
2. 1000 >> 6 % 64 == 15 在slots[15]
3. 1000 >> 0 % 64 == 40 在slots[40]

04 summary索引

summary索引采用radix tree实现，但在树的叶子节点时，存储的并不是数字而是docid对应的全部值和值长度

其中，_accessor->ReadData(localDocId, value, size);根据docid获取summary信息，对于DeserializeSummary的代码如下：

对summary信息进行反序列之后，使用迭代器(游标)逐步遍历value，并将其set进doc，每个字段之间使用0X80分隔符。

这里需注意的是，summary索引所有字段均会被转换成StringView类型，该类型的定义为

span 是 C++20 中引入的一个新的标准容器，它用于表示连续的一段内存区间，类似于一个轻量级的只读数组容器。

span 是一个轻量级的非拥有式容器，它提供了对连续内存的引用。span 的主要用途是作为函数参数，可以避免不必要的内存拷贝，并且可以防止悬垂指针和空指针引用的问题

参考文献

[1] git@github.com:alibaba/havenask.git
[2] https://blog.csdn.net/qq_41583040/article/details/130416816