漫画算法与数据结构（大规模数据集）

《漫画算法与数据结构（大规模数据集）》的重点并不是介绍通用的数据结构与算法分析。在大数据和人工智能的时代背景下，传统的经典算法往往性能不佳，甚至可能不起作用。本书以分布式数据集、流式数据结构与算法设计为主线，对流式数据采集、数据库中的数据结构设计、外部存储器算法进行介绍。目前，实际生产中已经形成了流式数据采集、存储、分析和计算的产品且成果显著。针对流式数据的采集和存储的产品主要有 Apache Kafka、Apache Pulsar 和 Pravega。流式数据的计算与分析主要经历了两代产品，第一代为 Apache Storm、Spark Streaming，目前流行的是第二代产品 Apache Flink。此外，还出现了 MPP(Shared Nothing 架构)的分布式并行架构数据库集群，主要有 Greenplum、HAWQ、HashData 等分布式数据库系统。通过在 MPP 架构基础上对流式数据的存储和计算支持，单节点每秒可处理多达 100 亿行数据，支持大规模数据实时写入且保证秒级实时性，主要的产品有Apache Doris、StarRocks 和 MatrixDB。这些优秀的产品无不把流式数据的数据结构和算法体现得淋漓尽致。本书针对流式数据场景，对常见的大规模数据集算法和数据结构进行了梳理和讲解。这些流式数据产品的出现有效解决了海量流式数据的采集、存储和极速全场景分析计算等问题。本书可作为从事算法设计与分析、大数据平台分析、模式识别与人工智能和数据库等领域研究工作的工程师、计算机科学家的参考书。

当应用于大型分布式数据集时，标准算法和数据结构可能会变慢或完全失效。选择专为大数据设计的算法可以节省时间、提高准确性并降低处理成本。《漫画算法与数据结构（大规模数据集）》将最前沿的研究论文提炼为实用的技术，用于绘制、流式传输并组织磁盘和云中的大规模数据集，十分独特。
大规模数据集的算法与数据结构为大型分布式数据引入了处理和分析技术。《漫画算法与数据结构（大规模数据集）》作为指南，包含了行业故事和有趣的插图，使复杂的概念也易于理解。在学习如何将强大的算法(如Bloom 过滤器、计数最小草图、HyperLogLog和LSM树)映射到你自己的用例时，将对真实世界的示例进行探索。
主要内容：
● 概率草图数据结构
● 选择正确的数据库引擎
● 设计高效的磁盘数据结构和算法
● 大规模系统中的算法权衡
● 有限空间资源下的百分位数计算
Python、R和伪代码中的示例。

Dzejla Medjedovic在纽约石溪大学应用算法实验室获得博士学位。
Emin Tahirovic在宾夕法尼亚大学获得了生物统计学博士学位。
插图画家
Ines Dedovic在德国亚琛RWTH大学成像和计算机视觉研究所获得博士学位。

第Ⅰ部分基于哈希的草图
第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

本书旨在帮助人们构建可扩展的应用程序并了解大规模数据系统下的算法构建块。本书涵盖了构建大规模应用程序的不同算法，包括使用概率数据结构节省空间、处理流式数据、使用磁盘上的数据以及了解数据库系统中的性能权衡。
本书读者对象
本书适合了解基本数据结构和算法的读者。书中的许多内容都以早期数据结构/算法课程中通常涵盖的内容为基础：大部分章节都从展示问题的传统解决方案开始并说明该算法或数据结构在大规模数据的背景下失败的原因。尽管各章的介绍部分讨论了一些基本算法，但这些内容只是对读者本应了解的主题的简短复习。本书的读者还应该掌握中级编程知识以及基本的概率知识。除了需要熟悉Python和伪代码这些基本知识，学习本书无须了解其他任何特定系统或架构(这就是算法的奥妙之处)。
本书主要结构
本书分为3 部分，共11 章。第Ⅰ部分介绍概率型简洁数据结构，第Ⅱ部分介绍流式数据结构和算法，第Ⅲ部分介绍外部存储器数据结构和算法。以下是各章内容的简要说明。
第Ⅰ部分：基于哈希的草图
??第1 章解释大规模数据在现代系统中存在严峻挑战的原因，以及这些挑战对算法和数据结构设计的影响。
??第2 章回顾哈希并解释哈希表如何发展以满足大型数据集和复杂分布式系统的需求(如一致性哈希)。哈希方法将在接下来的章节中大量使用，因此该章是第Ⅰ部分的基础。
??第3 章介绍近似成员关系问题和有助于解决该问题的两种数据结构：Bloom 过滤器和商过滤器。该章展示用例和误报率分析，以及使用每种数据结构的优缺点。
??第4 章描述频率估计问题并介绍count-min sketch(计数-最小草图，这是一种以非常节省空间的方式解决频率估计问题的数据结构)。该章讨论NLP、传感器数据和其他领域的用例，以及count-min sketch 在范围查询等问题中的应用。
第5 章深入了解基数估计、HyperLogLog 算法及其应用。该章通过一个小型实验，展示了从简单的概率计数到完整的HyperLogLog 数据结构在准确性方面的演变。
第Ⅱ部分：实时分析
??第6 章循序渐进地介绍数据流这一算法概念，以及其现实世界表现形式——流式数据(应用程序)。该章使用流式数据架构中的几个实际用例，展示了前几章中的数据结构如何用于流式数据上下文。
??第7 章介绍如何保留数据流中的代表性样本或数据流上的滑动窗口。该章指出人们何时可能对有偏差的样本感兴趣，并给出代码示例来展示如何实现将样本偏向于最近看到的数据元组。
??第8 章涉及计算连续数据流中数值数据的近似分位数，描述了两种草图数据结构：t-digest 和q-digest。该章还解释了它们背后的算法并在一个真实的数据集上将两者进行对比。
第Ⅲ部分：数据库的数据结构和外部存储器算法
??第9 章介绍外部存储器模型及相关示例，这些示例用于说明在远程存储上处理数据时，输入/输出成本如何支配CPU。
对于习惯于从CPU 成本方面考虑优化算法的算法设计者来说，该章会转换他们的视角。
??第10 章展示支持主流数据库的数据结构(例如，B 树和LSM树)，并且涵盖数据库引擎设计中的各种读/写权衡。从高层次上理解这些数据结构的工作原理有助于辨别不同风格的数据库，并为应用程序选择适合的数据库。
??第11 章着眼于对外部存储器的排序，并且展示了使用合并排序和快速排序的外部存储器优化版本对磁盘上的文件进行排序的最佳算法。该章以排序为例，说明在将批处理问题移至外部存储器时可以进行哪些优化。
本书的各部分相互关联，但第Ⅰ、Ⅱ部分之间的联系更紧密，因为这两部分都涉及RAM 中的数据结构以及在节省空间的同时最大限度地提高准确性这一主题。第Ⅲ部分具有独立的主题，只对它感兴趣的读者可以直接跳至这一部分。第Ⅰ、Ⅱ部分之间的阅读顺序也并不绝对，但先阅读第Ⅰ部分可能比直接跳入第Ⅱ部分更容易理解第Ⅱ部分。
第Ⅱ部分和第Ⅲ部分都以解释模型和背景的章节(第6 章和第9章)开始，强烈建议阅读这些章节，为理解相应部分中的其他章节奠定基础。了解这一点后，可以随意探索本书。编写时，我们尽力使各章自成体系。如果需要，可以随时返回前置章节以获取更多相关知识。我们建议所有读者阅读第1 章，因为该章解释了当涉及部署在繁忙的大型基础设施中的算法和数据结构时，大规模数据会产生范式转变的原因。
配套资源
书中示例的完整代码及配套资源可通过扫描本书封底的二维码获取并下载。
书中有几章包含代码，对于一些较复杂的算法以及上下文会明显加大代码复杂度的算法(如外部存储器算法)，我们会返回使用伪代码。我们将Python 和R 用于大多数代码片段，并在某些章节中用其创建一些小型实验来演示数据结构性能。读者应能够随意用自己选择的语言来实现编程练习，因为所涵盖的主题并不特定于某一语言或技术。
本书包含代码清单和类似普通文本形式的许多源代码示例。这两种情况下，源代码都被格式化为Courier New 字体，从而区分于普通文本。有时代码也以粗体突出显示与书中先前步骤相比发生变化的代码，例如将新特性添加到现有代码行时。
许多情况下，原始源代码已被重新格式化；我们添加了换行符并重新设置缩进以适合纸质书中可用的页面空间。极少数情况下，这些还不够，代码清单中还包含续行符(?)。此外，在正文中描述代码时，源代码中的注释通常已删除。不过许多代码清单都带有代码注释，突出了重要的概念。