Code-Life
Code-Life copied to clipboard
检索技术相关
检索技术核心
检索, 研究的是如何将所需的数据高效的取出来。
- 基础技术
- 进阶实战
- 系统案例
基础技术
- 数组 / 链表
- 二叉排序树
- 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分?
- 二分查找概率均匀
进阶实战
内存,随机访问效率高;磁盘顺序读写和内存差不多量级
- B+对海量磁盘数据建立索引
- 索引和数据分离
- 一个磁盘读取到内存的块中,存储多个元素(而不是单个元素)
- 节点分为内部节点和叶子节点
- 内部节点仅存储key和维持树形的指针, 叶子节点仅存储key和对应数据
- 叶子节点串成了有序的双向链表
- 对于一个 4 层的 B+ 树,每个节点大小为 4K,那么第一层根节点就是 4K,第二层最多有 400 个节点,一共就是 1.6M;第三层最多有 400^2,也就是 160000 个节点,一共就是 640M。对于现在常见的计算机来说,前三层的内部节点其实都可以存储在内存中。
- NoSql 日志系统用LSM树
- 将索引分为内存和磁盘两部分,并在内存达到阈值时启动树合并(Merge Trees)
- 用批量写入代替随机写入,并且用预写日志 WAL(Write Ahead Log) 技术保证内存数据,在系统崩溃后可以被恢复;
- 数据采取类似日志追加写的方式写入(Log Structured)磁盘,以顺序写的方式提高写入效率。