树结构
平衡二叉树
常用场景：内存内动态搜索某一数据
- 常用实现：
- AVL树：严格保持平衡
- 红黑树：删除后的旋转操作最多不超过3次
B-tree
常用场景：磁盘内搜索唯一性或重复性低的数据
- 优化结构：
- B+Tree：所有Key存在叶节点，所有叶节点多一个链指针
Trie树
常用场景：对大量字符串统计、排序
- 优化结构：
- Merkle Patricia Tree: 前缀树；通过hash连接子节点，防止链被篡改
- Double Array Trie：使用字符字典，根据状态转换机原理实现；优点是节约存储空间
索引结构
位图索引
常用场景：适用于OLAP场景，对高重复的数据进行条件筛选、聚合操作
- 优势：对distinct Key少的列，可以大量减少IO读取
- 劣势：
- 不适用唯一性或者重复率低的数据
- 索引大小与distinct Key数量呈线性关系
- 不适用有频繁DML（insert、update、delete）操作的数据
倒排索引
常用场景：全文索引，根据Key查询源数据记录
- 优势：适用于大数据量的源数据记录查找
- 劣势：
- 额外大量的存储开销
- 非实时，建立索引需要时间
哈希
BloomFilter
常用场景：判断数据是否存在，适用海量数据的筛选
- 优化结构：
- Counting BloomFilter：支持删除操作
- Spetral BloomFilter/Dynamic Count BloomFilter: 支持统计数据出现次数或者概率
- 优势：
- 降低hash冲突概率
- 劣势：
- 增加了存储开销
- 只能保证一定不存在的概率，仅适用不精确筛选的情况
