检索技术相关

[Draymonders]

检索技术核心

检索， 研究的是如何将所需的数据高效的取出来。

• 基础技术
• 进阶实战
• 系统案例

[Draymonders]

基础技术

• 数组 / 链表
• 二叉排序树
  • AVL / 红黑树
• 跳表
  • 以(1/2)^n的概率决定是否生成第n层, 近似log(n)的复杂度
• hash
  • 适合单体查询，丧失了范围检索
• bitmap
  • 位图，也就优化了1/32的空间
• bloom filter
  • 有错误率的存在，但检索的快， 而且删除操作(可以使用引用计数)很麻烦
• 倒排索引
  • <关键字， 文档Id, 关键字位置>
  • 前提需要排序
  • 作联合查询时，比如搜A和B，就是List<pair<关键字, 文档Id, 关键字位置>> pairA, pairB. 然后求pairA和pairB的共有的文档Id, 因此涉及到了多链表归并
• 利用上面所提到的数据结构对特定场景进行加速
  • pairA, pairB链表求交
• 联合查询加速
  • 调整次序法 A∩(B∪C)=(A∩B) ∪ (A∩C)
  • 快速多路归并法 (最小值所在的行的位置迅速跳转到大于等于{当前最大值}的位置)
  • 预先组合法 (大量出现A∩B∩C, 那么直接定义一个新key, 直接取结果)
  • 缓存法 (LRU进行缓存内容更换)

疑问

• 为什么用二分，而不用3-7分，or 4-6分？
  • 二分查找概率均匀

[Draymonders]

进阶实战

内存，随机访问效率高；磁盘顺序读写和内存差不多量级

• B+对海量磁盘数据建立索引
  • 索引和数据分离
  • 一个磁盘读取到内存的块中，存储多个元素（而不是单个元素）
  • 节点分为内部节点和叶子节点
    • 内部节点仅存储key和维持树形的指针, 叶子节点仅存储key和对应数据
    • 叶子节点串成了有序的双向链表
    • 对于一个 4 层的 B+ 树，每个节点大小为 4K，那么第一层根节点就是 4K，第二层最多有 400 个节点，一共就是 1.6M；第三层最多有 400^2，也就是 160000 个节点，一共就是 640M。对于现在常见的计算机来说，前三层的内部节点其实都可以存储在内存中。
• NoSql 日志系统用LSM树
  • 将索引分为内存和磁盘两部分，并在内存达到阈值时启动树合并（Merge Trees）
  • 用批量写入代替随机写入，并且用预写日志 WAL（Write Ahead Log） 技术保证内存数据，在系统崩溃后可以被恢复；
  • 数据采取类似日志追加写的方式写入（Log Structured）磁盘，以顺序写的方式提高写入效率。