索引与数据结构、并行算法
3. 索引与数据结构
- 索引类比目录：类似于书籍目录，帮助我们快速定位信息。
- 索引的核心目的：提升数据查找效率，优化增删改查性能。
- 实际应用广泛：MySQL、Redis、搜索引擎、分布式系统、中间件等。
3.1. 索引设计中的需求分析
1. 功能性需求
| 考虑因素 | 说明 |
| 数据结构化 | 是结构化数据（如表格）还是非结构化数据（如网页）？ |
| 数据动态性 | 是静态集合还是需要支持动态增删改查？ |
| 存储位置 | 存储在内存 or 磁盘 or 内存+磁盘混合？ |
| 查找类型 | 单值查找 or 区间查找？ |
| 查询组合 | 单关键词 or 多关键词组合？ |
2. 非功能性需求
| 考虑因素 | 说明 |
| 存储空间占用 | 特别是内存中索引的体积控制至关重要。 |
| 索引维护成本 | 动态更新带来的性能负担不容忽视。 |
3.2. 常用索引数据结构与场景分析
1. 散列表（Hash Table）
- 特点：查询效率高（O(1)），适合内存存储。
- 代表应用：Redis、Memcache。
- 限制：不支持区间查找，键需可哈希。
- 红黑树（Red-Black Tree）
- 特点：自平衡 BST，支持动态数据操作（O(logn)）。
- 代表应用：Linux Ext 文件系统的块索引。
- 适用场景：内存中的有序索引场景。
2. B+ 树
- 特点：适合磁盘存储、节点多叉、树高低、IO 次数少。
- 代表应用：MySQL、Oracle 数据库索引。
- 优点：高性能磁盘查找、支持范围查询。
- 缺点：实现复杂、维护成本高。
3. 跳表（Skip List）
- 特点：查询效率接近平衡树，支持动态操作。
- 代表应用：Redis 的
zset（有序集合）。 - 优点：实现简单、灵活调整空间效率。
- 缺点：最坏时间复杂度仍是 O(n)。
4. 位图（Bitmap）
- 特点：适合标记“存在/不存在”状态，支持快速定位。
- 应用场景：辅助索引、去重、统计频率。
5. 布隆过滤器（Bloom Filter）
- 特点：高效、占用空间少，判断“不存在”很准。
- 应用场景：提前过滤不在磁盘的数据，减少无效查询。
- 限制：存在误判（可能误报“存在”）。
6. 有序数组
- 特点：适用于静态数据，支持快速二分查找。
- 适用场景：查询频繁但不更新的数据集合。
- 限制：不支持动态插入删除。
应用场景对比总结：
| 数据结构 | 适用场景 | 优势 | 劣势 |
| 散列表 | 内存中的KV存储（如Redis） | 查询快，O(1) | 不支持区间查找 |
| 红黑树 | 内存中的有序数据索引 | 平衡查找，O(logn) | 深度可能较大 |
| B+树 | 磁盘中的数据库索引 | 多叉、低树高、IO少 | 实现复杂 |
| 跳表 | 有序集合，如Redis zset | 简单灵活 | 查询不稳定 |
| 位图 | 存在性标记、状态判断 | 空间小，效率高 | 适用范围有限 |
| 布隆过滤器 | 过滤“不存在”的数据 | 高效省内存 | 有误判，不可删除 |
| 有序数组 | 静态数据、查找密集 | 二分查找快 | 插入删除代价高 |
4. 并行算法
4.1. 并行算法概述
- 目的：当算法无法继续优化（例如已是 O(nlogn) 级别）时，仍可通过并行处理来显著提高执行效率。
- 本质：通过“数据分片 + 多线程并行执行”的策略，加快整体处理速度。
注意：时间复杂度 ≠ 实际性能。实际开发中，哪怕提升 10%-20%，也非常有意义。
- 核心思想：数据分片 + 并行执行
- 适用范围：
-
- 无依赖关系或依赖关系可控的任务
- 数据规模巨大（超内存或高 I/O 需求）
- 工程意义：
-
- 并行算法是一种工程优化思想，可结合多核资源提升性能
- 如 MapReduce 就是经典的并行计算框架
4.2. 典型应用场景与改造方式
1. 并行排序
场景：排序 8GB 数据，单机内存可容纳
方案一：并行归并排序
- 将数据划分为
16个500MB小集合 16个线程并行排序- 最后将
16个有序小集合合并为一个大集合
方案二：并行快速排序
- 扫描一遍数据，划分成
16个有序区间 - 每个区间用单独线程排序
- 排完即为整体有序，无需额外合并
对比总结：
| 类型 | 特点 |
| 并行归并 | 先分片，后合并 |
| 并行快排 | 先分区间，后排序，无需合并 |
- 本质都基于“分治 + 并行”的思想
- 若数据规模为
1TB，关键变为减少磁盘 I/O 操作，而不是 CPU 执行效率。
2. 并行查找（散列表优化）
背景问题：
- 散列表动态扩容慢、耗内存（如将 2GB 扩到 3GB，利用率低）
优化策略：
- 将数据随机分成
k=16份，每份构建一个小散列表 - 优点：
-
- 每个小散列表内存更易管理
- 扩容时只需局部扩容（如 150MB 扩到 225MB）
- 并行查找：启动
16个线程同时搜索 16 个小散列表 - 查找效率可能更高
- 添加新数据时放入装载因子最小的散列表以降低冲突率
3. 并行字符串匹配
场景：
- 关键词搜索在超大文本中非常耗时
优化方案：
- 将大文本划分为
k=16份，启动16个线程并行匹配关键词
细节处理：
- 跨分片的关键词可能被分割（匹配失败）
- 解决方式：
-
- 关键词长度为
m - 每两个分片间拼接边缘
2m长度的新串，再额外查找一次
- 关键词长度为
4. 并行广度优先搜索（Parallel BFS）
原理：
- BFS 本身是“逐层搜索”，适合并行
并行改造：
- 使用两个队列 A、B
-
- 并行扩展 A 中所有节点 → 结果放入 B
- 清空 A，再并行扩展 B 中节点 → 放入 A
- 如此交替，直到搜索结束