一些常用数据结构。
Bloom Filters
回答某一个元素是否存在于集合中。若布隆过滤器判断不存在，则元素一定不存在；反之，并不能确定元素一定存在于集合中/
布隆过滤器组成：
- 一长串bit
- 一组哈希函数
布隆过滤器插入元素：
- 经过哈希函数计算出所有需要置1的bit位；
- 所有位置1.
布隆过滤器查询元素：
- 计算所有应该为1的bit位；
- 判断是否指定位均为1:
- 如果是，需要进一步检查元素是否真的存在；
- 如果不是，则元素一定不存在。
难以删除，删除条目需要重新构建。
Skip Lists
跳表：在链表基础上对查询进行的改进，以将查询平均时间复杂度。等同于在有序链表基础上加入多级索引，通过这些索引能够快速访问底层链表的某些位置。
- 一级：包含所有元素的链表；
- 二级：在一级链表的基础上跳过所有的相邻元素；
- 三级：在二级链表的基础上继续跳过所有相邻元素；
。。。 - 每个层级都将包含更低层级的一半元素。
上述构建过程所得跳表，可以是查找时间复杂度降低为O(logn)，常被用于构建LSM Tree的Mem Table。
删除
- 首先标记节点为逻辑删除；
- 确定没有其他线程访问后，将其物理删除。
如图所示，首先将K5删除标记为置为true，然后可以自顶向下开始，逐步使用cas将指向K5的指针修改，进而跳表物理结构得到修改。
最后确认无线程访问K5后，将其delete。
Trie / Radix Trees
Trie结构：
- 垂直方向压缩：如上图所示，三个key包含多个重复前缀0，实际上可以压缩为一种表示。
- 水平方向压缩：转化为二进制后，改位要么0要么1，因此无需具体存储该位具体是0或者1，只需要定义左指针指向0右指针指向1，不影响比较和还原。
带路径压缩的Trie，即Radix Tree（基数树），每层不再是比较单个字符，而可能是一连串字符串。
示例：
实现时可以对何时进行上层合并进行配置。
Inverted Indexes
思路：对给定属性值中的子元素（术语）进行映射，此后可以对指定术语进行快速索引。
- Dictionary：包含术语，以及术语词频；
- Posting Lists：所有包含该术语的元组ID。
Lucene
- 右边指出了我们如何加速在Dictionary中查找指定key对应的偏移量的过程。
Postgres
pg使用B+树用作术语字典，字典将映射到一个posting list。
posting list：形式随着其中record数量的变化而变化
- 少量record：由record id组成的有序列表；
- 大量record：由record id组成的b+树。
此外还有一个pending list，即变更日志，用于降低字典更新频率。
Vector Indexes
向量检索：一种基于“语义向量相似度”的搜索方法。把文本、图片、音频等对象通过模型编码为高维向量（embedding），再用向量之间的距离/相似度来找“最相近”的内容。
目标：解决传统检索（倒排索引）中只能匹配字面词、无法匹配语义相同但字面不同的文本。
一些方法：
- 倒排文件（inverted file）：将所有向量以K-means或其他聚类方法分成小的group，使用相同的聚类算法将查询向量映射到某个group，然后扫描该group中的向量进行匹配，为了提高准确性，也可以额外扫描临近group；
- 小世界（small world）：构建图，其中途中每个节点代表一个向量，且具备n条边指向其邻居（图可以构建为多层），对于给定查询向量，其在同样可能被映射到某个位置，查询将从指定的入口节点开始，使用贪心算法记录那些距离查询向量更接近的节点，并在远离查询向量时停止。