目 录

第Ⅰ部分基于哈希的草图

第1 章 导论     3

1.1 示例     5

1.1.1 示例解决方法  6

1.1.2 本书给出的解决方法     8

1.2 本书的结构    11

1.3 本书的不同之处及目标读者    12

1.4 为什么大规模数据对当今的系统如此具有挑战性     13

1.4.1 CPU 内存性能差距    13

1.4.2 内存层次结构   14

1.4.3 延迟与带宽   15

1.4.4 分布式系统的情况    15

1.5 基于硬件来设计算法     16

1.6 本章小结     17

第2 章 哈希表和现代哈希回顾     19

2.1 无处不在的哈希  20

2.2 数据结构概述   22

2.3 现代系统中的使用场景     25

2.3.1 备份/存储解决方案中的重复数据删除   25

2.3.2 使用MOSS 和Rabin-Karp 指纹识别进行剽窃检测   26

2.4 有关O(1)      29

2.5 解决冲突：理论与实践     30

2.6 使用场景：Python 的dict是如何实现的   33

2.7 MurmurHash    35

2.8 分布式系统的哈希表：一致性哈希   36

2.8.1 一个典型的哈希问题    37

2.8.2 哈希环    38

2.8.3 查找    41

2.8.4 添加新节点/资源    41

2.8.5 删除节点   44

2.8.6 一致性哈希场景：Chord      48

2.8.7 一致性哈希：编程练习    50

2.9 本章小结    50

第3 章 近似成员关系：Bloom 过滤器和商

过滤器   53

3.1 工作原理    56

3.1.1 插入    56

3.1.2 查找    57

3.2 用例     58

3.2.1 网络中的Bloom 过滤器：Squid  58

3.2.2 Bitcoin 移动应用    59

3.3 一个简单的实现  60

3.4 设置Bloom过滤器     61

3.5 一点理论     66

3.6 Bloom 过滤器的调整和替代方案   69

3.7 商过滤器     70

3.7.1 商-余数法   71

3.7.2 了解元数据位  73

3.7.3 示例：插入商过滤器中  73

3.7.4 用于查找的Python代码   76

3.7.5 调整大小与合并   79

3.7.6 误报率和空间考虑   80

3.8 Bloom 过滤器和商过滤器的比较   80

3.9 本章小结     82

第4 章 频率估计和count-minsketch    85

4.1 多数元素     87

4.2 count-min sketch 的工作原理     90

4.2.1 update     90

4.2.2 estimate    91

4.3 用例     92

4.3.1 前k 个睡眠不安者   92

4.3.2 缩放单词的分布相似度    96

4.4 count-min sketch 中的误差与空间   99

4.5 count-min sketch 的简单实现   100

4.5.1 练习     101

4.5.2 公式所蕴含的原理   102

4.6 使用count-min sketch进行范围查询  103

4.6.1 二元区间   104

4.6.2 更新阶段   105

4.6.3 估计阶段   107

4.6.4 计算二元区间     108

4.7 本章小结    110

第5 章 基数估计和HyperLogLog  113

5.1 对数据库中的不同项计数     114

5.2 HyperLogLog 增量设计    116

5.2.1 第一步：概率计数     117

5.2.2 随机平均   119

5.2.3 LogLog    121

5.2.4 HyperLogLog：使用调和平均值进行随机平均   123

5.3 用例：使用HLL 捕捉蠕虫     126

5.4 一个小实验  128

5.5 用例：使用Hyper-LogLog 进行聚合  132

5.6 本章小结   135

第Ⅱ部分实时分析第6 章 流式数据   139

6.1 流式数据系统：元示例   144

6.1.1 Bloom 连接  144

6.1.2 重复数据删除     147

6.1.3 负载平衡和跟踪网络流量   149

6.2 数据流中的实际约束和概念   151

6.2.1 实时     151

6.2.2 小时间和小空间   152

6.2.3 概念转变和概念漂移     152

6.2.4 滑动窗口模型     153

6.3 抽样和估计  155

6.3.1 有偏差抽样策略     157

6.3.2 代表性样本的估计     160

6.4 本章小结    162

第7 章 从数据流中抽样   165

7.1 从地标流中抽样  166

7.1.1 伯努利抽样  166

7.1.2 蓄水池抽样  170

7.1.3 有偏差的蓄水池抽样     176

7.2 从滑动窗口抽样  182

7.2.1 链式抽样   182

7.2.2 优先级抽样  187

7.3 抽样算法比较  191

7.4 本章小结    195

第8 章 数据流上的近似分位数     197

8.1 精确分位数  198

8.2 近似分位数  201

8.2.1 加法误差   201

8.2.2 相对误差   203

8.2.3 数据域中的相对误差     204

8.3 t-digest：工作

原理    204

8.3.1 digest     205

8.3.2 比例函数   207

8.3.3 合并t-digest  211

8.3.4 t-digest 的空间范围    215

8.4 q-digest    215

8.4.1 从头开始构建q-digest    216

8.4.2 合并q-digest    218

8.4.3 q-digest 中的误差和空间注意事项    219

8.4.4 使用q-digest 进行分位数查询  220

8.5 模拟代码和结果  221

8.6 本章小结   226

第Ⅲ部分数据库的数据结构和外部存储器算法

第9 章 外部存储器模型  231

9.1 外部存储器模型初探     233

9.2 示例1：寻找最小值     235

9.3 示例2：二进制搜索     239

9.3.1 生物信息学用例    239

9.3.2 运行时间分析     241

9.4 最优搜索    243

9.5 示例3：合并K 个排序列表   246

9.5.1 合并时间/日期日志     246

9.5.2 外部存储器模型是否过于简单  250

9.6 下一章内容  251

9.7 本章小结    251

第10 章 数据库的数据结构：B 树、Bε 树和LSM 树   253

10.1 索引的工作原理    254

10.2 本章中的数据结构    256

10.3 B 树    258

10.3.1 B 树平衡  259

10.3.2 查找   260

10.3.3 插入   261

10.3.4 删除   263

10.3.5 B+树   266

10.3.6 B+树上的操作有何不同   268

10.3.7 用例：MySQL 等中的B 树   268

10.4 为什么B 树查找在外部存储器中是最佳的   269

10.5 Bε 树    272

10.5.1 Bε 树：工作原理   273

10.5.2 缓冲区机制· 273

10.5.3 插入和删除  275

10.5.4 查找   276

10.5.5 成本分析  277

10.5.6 Bε 树：数据结构的范围  278

10.5.7 用例：TokuDB 中的Bε 树   279

10.5.8 输入/输出之道：欲速则不达  280

10.6 日志结构合并树(LSM 树)    281

10.6.1 LSM 树：工作原理   283

10.6.2 LSM 树成本分析   285

10.6.3 用例：Cassandra 中的LSM 树  286

10.7 本章小结   287

第11 章 外部存储器排序    289

11.1 排序用例   290

11.1.1 机器人运动规划    290

11.1.2 癌症基因组学   291

11.2 外部存储器排序的挑战：示例   293

11.3 外部存储器合并排序    297

11.4 外部快速排序 300

11.4.1 外部存储器双向快速排序  301

11.4.2 外部存储器多向快速排序  302

11.4.3 找到足够的枢轴   303

11.4.4 找到足够好的枢轴   304

11.4.5 将它们重新组合在一起   305

11.5 为什么外部存储器合并排序是最优的   306

11.6 结尾    308

11.7 本章小结   309

参考文献      310