當(dāng)應(yīng)用于大型分布式數(shù)據(jù)集時，標(biāo)準算法和數(shù)據(jù)結(jié)構(gòu)可能會變慢或完全失效。選擇專為大數(shù)據(jù)設(shè)計的算法可以節(jié)省時間、提高準確性并降低處理成本。《漫畫算法與數(shù)據(jù)結(jié)構(gòu)（大規(guī)模數(shù)據(jù)集）》將最前沿的研究論文提煉為實用的技術(shù)，用于繪制、流式傳輸并組織磁盤和云中的大規(guī)模數(shù)據(jù)集，十分獨特。
大規(guī)模數(shù)據(jù)集的算法與數(shù)據(jù)結(jié)構(gòu)為大型分布式數(shù)據(jù)引入了處理和分析技術(shù)�！堵�畫算法與數(shù)據(jù)結(jié)構(gòu)（大規(guī)模數(shù)據(jù)集）》作為指南，包含了行業(yè)故事和有趣的插圖，使復(fù)雜的概念也易于理解。在學(xué)習(xí)如何將強大的算法(如Bloom 過濾器、計數(shù)最小草圖、HyperLogLog和LSM樹)映射到你自己的用例時，將對真實世界的示例進行探索。
主要內(nèi)容：
● 概率草圖數(shù)據(jù)結(jié)構(gòu)
● 選擇正確的數(shù)據(jù)庫引擎
● 設(shè)計高效的磁盤數(shù)據(jù)結(jié)構(gòu)和算法
● 大規(guī)模系統(tǒng)中的算法權(quán)衡
● 有限空間資源下的百分位數(shù)計算
Python、R和偽代碼中的示例。

《漫畫算法與數(shù)據(jù)結(jié)構(gòu)（大規(guī)模數(shù)據(jù)集）》的重點并不是介紹通用的數(shù)據(jù)結(jié)構(gòu)與算法分析。在大數(shù)據(jù)和人工智能的時代背景下，傳統(tǒng)的經(jīng)典算法往往性能不佳，甚至可能不起作用。本書以分布式數(shù)據(jù)集、流式數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計為主線，對流式數(shù)據(jù)采集、數(shù)據(jù)庫中的數(shù)據(jù)結(jié)構(gòu)設(shè)計、外部存儲器算法進行介紹。目前，實際生產(chǎn)中已經(jīng)形成了流式數(shù)據(jù)采集、存儲、分析和計算的產(chǎn)品且成果顯著。針對流式數(shù)據(jù)的采集和存儲的產(chǎn)品主要有 Apache Kafka、Apache Pulsar 和 Pravega。流式數(shù)據(jù)的計算與分析主要經(jīng)歷了兩代產(chǎn)品，第一代為 Apache Storm、Spark Streaming，目前流行的是第二代產(chǎn)品 Apache Flink。此外，還出現(xiàn)了 MPP(Shared Nothing 架構(gòu))的分布式并行架構(gòu)數(shù)據(jù)庫集群，主要有 Greenplum、HAWQ、HashData 等分布式數(shù)據(jù)庫系統(tǒng)。通過在 MPP 架構(gòu)基礎(chǔ)上對流式數(shù)據(jù)的存儲和計算支持，單節(jié)點每秒可處理多達 100 億行數(shù)據(jù)，支持大規(guī)模數(shù)據(jù)實時寫入且保證秒級實時性，主要的產(chǎn)品有Apache Doris、StarRocks 和 MatrixDB。這些優(yōu)秀的產(chǎn)品無不把流式數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)和算法體現(xiàn)得淋漓盡致。本書針對流式數(shù)據(jù)場景，對常見的大規(guī)模數(shù)據(jù)集算法和數(shù)據(jù)結(jié)構(gòu)進行了梳理和講解。這些流式數(shù)據(jù)產(chǎn)品的出現(xiàn)有效解決了海量流式數(shù)據(jù)的采集、存儲和極速全場景分析計算等問題。本書可作為從事算法設(shè)計與分析、大數(shù)據(jù)平臺分析、模式識別與人工智能和數(shù)據(jù)庫等領(lǐng)域研究工作的工程師、計算機科學(xué)家的參考書。

本書旨在幫助人們構(gòu)建可擴展的應(yīng)用程序并了解大規(guī)模數(shù)據(jù)系統(tǒng)下的算法構(gòu)建塊。本書涵蓋了構(gòu)建大規(guī)模應(yīng)用程序的不同算法，包括使用概率數(shù)據(jù)結(jié)構(gòu)節(jié)省空間、處理流式數(shù)據(jù)、使用磁盤上的數(shù)據(jù)以及了解數(shù)據(jù)庫系統(tǒng)中的性能權(quán)衡。
本書讀者對象
本書適合了解基本數(shù)據(jù)結(jié)構(gòu)和算法的讀者。書中的許多內(nèi)容都以早期數(shù)據(jù)結(jié)構(gòu)/算法課程中通常涵蓋的內(nèi)容為基礎(chǔ)：大部分章節(jié)都從展示問題的傳統(tǒng)解決方案開始并說明該算法或數(shù)據(jù)結(jié)構(gòu)在大規(guī)模數(shù)據(jù)的背景下失敗的原因。盡管各章的介紹部分討論了一些基本算法，但這些內(nèi)容只是對讀者本應(yīng)了解的主題的簡短復(fù)習(xí)。本書的讀者還應(yīng)該掌握中級編程知識以及基本的概率知識。除了需要熟悉Python和偽代碼這些基本知識，學(xué)習(xí)本書無須了解其他任何特定系統(tǒng)或架構(gòu)(這就是算法的奧妙之處)。
本書主要結(jié)構(gòu)
本書分為3 部分，共11 章。第Ⅰ部分介紹概率型簡潔數(shù)據(jù)結(jié)構(gòu)，第Ⅱ部分介紹流式數(shù)據(jù)結(jié)構(gòu)和算法，第Ⅲ部分介紹外部存儲器數(shù)據(jù)結(jié)構(gòu)和算法。以下是各章內(nèi)容的簡要說明。
第Ⅰ部分：基于哈希的草圖
??第1 章解釋大規(guī)模數(shù)據(jù)在現(xiàn)代系統(tǒng)中存在嚴峻挑戰(zhàn)的原因，以及這些挑戰(zhàn)對算法和數(shù)據(jù)結(jié)構(gòu)設(shè)計的影響。
??第2 章回顧哈希并解釋哈希表如何發(fā)展以滿足大型數(shù)據(jù)集和復(fù)雜分布式系統(tǒng)的需求(如一致性哈希)。哈希方法將在接下來的章節(jié)中大量使用，因此該章是第Ⅰ部分的基礎(chǔ)。
??第3 章介紹近似成員關(guān)系問題和有助于解決該問題的兩種數(shù)據(jù)結(jié)構(gòu)：Bloom 過濾器和商過濾器。該章展示用例和誤報率分析，以及使用每種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點。
??第4 章描述頻率估計問題并介紹count-min sketch(計數(shù)-最小草圖，這是一種以非常節(jié)省空間的方式解決頻率估計問題的數(shù)據(jù)結(jié)構(gòu))。該章討論NLP、傳感器數(shù)據(jù)和其他領(lǐng)域的用例，以及count-min sketch 在范圍查詢等問題中的應(yīng)用。
第5 章深入了解基數(shù)估計、HyperLogLog 算法及其應(yīng)用。該章通過一個小型實驗，展示了從簡單的概率計數(shù)到完整的HyperLogLog 數(shù)據(jù)結(jié)構(gòu)在準確性方面的演變。
第Ⅱ部分：實時分析
??第6 章循序漸進地介紹數(shù)據(jù)流這一算法概念，以及其現(xiàn)實世界表現(xiàn)形式流式數(shù)據(jù)(應(yīng)用程序)。該章使用流式數(shù)據(jù)架構(gòu)中的幾個實際用例，展示了前幾章中的數(shù)據(jù)結(jié)構(gòu)如何用于流式數(shù)據(jù)上下文。
??第7 章介紹如何保留數(shù)據(jù)流中的代表性樣本或數(shù)據(jù)流上的滑動窗口。該章指出人們何時可能對有偏差的樣本感興趣，并給出代碼示例來展示如何實現(xiàn)將樣本偏向于最近看到的數(shù)據(jù)元組。
??第8 章涉及計算連續(xù)數(shù)據(jù)流中數(shù)值數(shù)據(jù)的近似分位數(shù)，描述了兩種草圖數(shù)據(jù)結(jié)構(gòu)：t-digest 和q-digest。該章還解釋了它們背后的算法并在一個真實的數(shù)據(jù)集上將兩者進行對比。
第Ⅲ部分：數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)和外部存儲器算法
??第9 章介紹外部存儲器模型及相關(guān)示例，這些示例用于說明在遠程存儲上處理數(shù)據(jù)時，輸入/輸出成本如何支配CPU。
對于習(xí)慣于從CPU 成本方面考慮優(yōu)化算法的算法設(shè)計者來說，該章會轉(zhuǎn)換他們的視角。
??第10 章展示支持主流數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)(例如，B 樹和LSM樹)，并且涵蓋數(shù)據(jù)庫引擎設(shè)計中的各種讀/寫權(quán)衡。從高層次上理解這些數(shù)據(jù)結(jié)構(gòu)的工作原理有助于辨別不同風(fēng)格的數(shù)據(jù)庫，并為應(yīng)用程序選擇適合的數(shù)據(jù)庫。
??第11 章著眼于對外部存儲器的排序，并且展示了使用合并排序和快速排序的外部存儲器優(yōu)化版本對磁盤上的文件進行排序的最佳算法。該章以排序為例，說明在將批處理問題移至外部存儲器時可以進行哪些優(yōu)化。
本書的各部分相互關(guān)聯(lián)，但第Ⅰ、Ⅱ部分之間的聯(lián)系更緊密，因為這兩部分都涉及RAM 中的數(shù)據(jù)結(jié)構(gòu)以及在節(jié)省空間的同時最大限度地提高準確性這一主題。第Ⅲ部分具有獨立的主題，只對它感興趣的讀者可以直接跳至這一部分。第Ⅰ、Ⅱ部分之間的閱讀順序也并不絕對，但先閱讀第Ⅰ部分可能比直接跳入第Ⅱ部分更容易理解第Ⅱ部分。
第Ⅱ部分和第Ⅲ部分都以解釋模型和背景的章節(jié)(第6 章和第9章)開始，強烈建議閱讀這些章節(jié)，為理解相應(yīng)部分中的其他章節(jié)奠定基礎(chǔ)。了解這一點后，可以隨意探索本書。編寫時，我們盡力使各章自成體系。如果需要，可以隨時返回前置章節(jié)以獲取更多相關(guān)知識。我們建議所有讀者閱讀第1 章，因為該章解釋了當(dāng)涉及部署在繁忙的大型基礎(chǔ)設(shè)施中的算法和數(shù)據(jù)結(jié)構(gòu)時，大規(guī)模數(shù)據(jù)會產(chǎn)生范式轉(zhuǎn)變的原因。
配套資源
書中示例的完整代碼及配套資源可通過掃描本書封底的二維碼獲取并下載。
書中有幾章包含代碼，對于一些較復(fù)雜的算法以及上下文會明顯加大代碼復(fù)雜度的算法(如外部存儲器算法)，我們會返回使用偽代碼。我們將Python 和R 用于大多數(shù)代碼片段，并在某些章節(jié)中用其創(chuàng)建一些小型實驗來演示數(shù)據(jù)結(jié)構(gòu)性能。讀者應(yīng)能夠隨意用自己選擇的語言來實現(xiàn)編程練習(xí)，因為所涵蓋的主題并不特定于某一語言或技術(shù)。
本書包含代碼清單和類似普通文本形式的許多源代碼示例。這兩種情況下，源代碼都被格式化為Courier New 字體，從而區(qū)分于普通文本。有時代碼也以粗體突出顯示與書中先前步驟相比發(fā)生變化的代碼，例如將新特性添加到現(xiàn)有代碼行時。
許多情況下，原始源代碼已被重新格式化；我們添加了換行符并重新設(shè)置縮進以適合紙質(zhì)書中可用的頁面空間。極少數(shù)情況下，這些還不夠，代碼清單中還包含續(xù)行符(?)。此外，在正文中描述代碼時，源代碼中的注釋通常已刪除。不過許多代碼清單都帶有代碼注釋，突出了重要的概念。

Dzejla Medjedovic在紐約石溪大學(xué)應(yīng)用算法實驗室獲得博士學(xué)位。
Emin Tahirovic在賓夕法尼亞大學(xué)獲得了生物統(tǒng)計學(xué)博士學(xué)位。
插圖畫家
Ines Dedovic在德國亞琛RWTH大學(xué)成像和計算機視覺研究所獲得博士學(xué)位。

第Ⅰ部分基于哈希的草圖
第1 章 導(dǎo)論 3
1.1 示例 5
1.1.1 示例解決方法 6
1.1.2 本書給出的解決方法 8
1.2 本書的結(jié)構(gòu) 11
1.3 本書的不同之處及目標(biāo)讀者 12
1.4 為什么大規(guī)模數(shù)據(jù)對當(dāng)今的系統(tǒng)如此具有挑戰(zhàn)性 13
1.4.1 CPU 內(nèi)存性能差距 13
1.4.2 內(nèi)存層次結(jié)構(gòu) 14
1.4.3 延遲與帶寬 15
1.4.4 分布式系統(tǒng)的情況 15
1.5 基于硬件來設(shè)計算法 16
1.6 本章小結(jié) 17
第2 章 哈希表和現(xiàn)代哈希回顧 19
2.1 無處不在的哈希 20
2.2 數(shù)據(jù)結(jié)構(gòu)概述 22
2.3 現(xiàn)代系統(tǒng)中的使用場景 25
2.3.1 備份/存儲解決方案中的重復(fù)數(shù)據(jù)刪除 25
2.3.2 使用MOSS 和Rabin-Karp 指紋識別進行剽竊檢測 26
2.4 有關(guān)O(1) 29
2.5 解決沖突：理論與實踐 30
2.6 使用場景：Python 的dict是如何實現(xiàn)的 33
2.7 MurmurHash 35
2.8 分布式系統(tǒng)的哈希表：一致性哈希 36
2.8.1 一個典型的哈希問題 37
2.8.2 哈希環(huán) 38
2.8.3 查找 41
2.8.4 添加新節(jié)點/資源 41
2.8.5 刪除節(jié)點 44
2.8.6 一致性哈希場景：Chord 48
2.8.7 一致性哈希：編程練習(xí) 50
2.9 本章小結(jié) 50
第3 章 近似成員關(guān)系：Bloom 過濾器和商
過濾器 53
3.1 工作原理 56
3.1.1 插入 56
3.1.2 查找 57
3.2 用例 58
3.2.1 網(wǎng)絡(luò)中的Bloom 過濾器：Squid 58
3.2.2 Bitcoin 移動應(yīng)用 59
3.3 一個簡單的實現(xiàn) 60
3.4 設(shè)置Bloom過濾器 61
3.5 一點理論 66
3.6 Bloom 過濾器的調(diào)整和替代方案 69
3.7 商過濾器 70
3.7.1 商-余數(shù)法 71
3.7.2 了解元數(shù)據(jù)位 73
3.7.3 示例：插入商過濾器中 73
3.7.4 用于查找的Python代碼 76
3.7.5 調(diào)整大小與合并 79
3.7.6 誤報率和空間考慮 80
3.8 Bloom 過濾器和商過濾器的比較 80
3.9 本章小結(jié) 82
第4 章 頻率估計和count-minsketch 85
4.1 多數(shù)元素 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 的簡單實現(xiàn) 100
4.5.1 練習(xí) 101
4.5.2 公式所蘊含的原理 102
4.6 使用count-min sketch進行范圍查詢 103
4.6.1 二元區(qū)間 104
4.6.2 更新階段 105
4.6.3 估計階段 107
4.6.4 計算二元區(qū)間 108
4.7 本章小結(jié) 110
第5 章 基數(shù)估計和HyperLogLog 113
5.1 對數(shù)據(jù)庫中的不同項計數(shù) 114
5.2 HyperLogLog 增量設(shè)計 116
5.2.1 第一步：概率計數(shù) 117
5.2.2 隨機平均 119
5.2.3 LogLog 121
5.2.4 HyperLogLog：使用調(diào)和平均值進行隨機平均 123
5.3 用例：使用HLL 捕捉蠕蟲 126
5.4 一個小實驗 128
5.5 用例：使用Hyper-LogLog 進行聚合 132
5.6 本章小結(jié) 135
第Ⅱ部分實時分析第6 章 流式數(shù)據(jù) 139
6.1 流式數(shù)據(jù)系統(tǒng)：元示例 144
6.1.1 Bloom 連接 144
6.1.2 重復(fù)數(shù)據(jù)刪除 147
6.1.3 負載平衡和跟蹤網(wǎng)絡(luò)流量 149
6.2 數(shù)據(jù)流中的實際約束和概念 151
6.2.1 實時 151
6.2.2 小時間和小空間 152
6.2.3 概念轉(zhuǎn)變和概念漂移 152
6.2.4 滑動窗口模型 153
6.3 抽樣和估計 155
6.3.1 有偏差抽樣策略 157
6.3.2 代表性樣本的估計 160
6.4 本章小結(jié) 162
第7 章 從數(shù)據(jù)流中抽樣 165
7.1 從地標(biāo)流中抽樣 166
7.1.1 伯努利抽樣 166
7.1.2 蓄水池抽樣 170
7.1.3 有偏差的蓄水池抽樣 176
7.2 從滑動窗口抽樣 182
7.2.1 鏈式抽樣 182
7.2.2 優(yōu)先級抽樣 187
7.3 抽樣算法比較 191
7.4 本章小結(jié) 195
第8 章 數(shù)據(jù)流上的近似分位數(shù) 197
8.1 精確分位數(shù) 198
8.2 近似分位數(shù) 201
8.2.1 加法誤差 201
8.2.2 相對誤差 203
8.2.3 數(shù)據(jù)域中的相對誤差 204
8.3 t-digest：工作
原理 204
8.3.1 digest 205
8.3.2 比例函數(shù) 207
8.3.3 合并t-digest 211
8.3.4 t-digest 的空間范圍 215
8.4 q-digest 215
8.4.1 從頭開始構(gòu)建q-digest 216
8.4.2 合并q-digest 218
8.4.3 q-digest 中的誤差和空間注意事項 219
8.4.4 使用q-digest 進行分位數(shù)查詢 220
8.5 模擬代碼和結(jié)果 221
8.6 本章小結(jié) 226
第Ⅲ部分數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)和外部存儲器算法

第9 章 外部存儲器模型 231
9.1 外部存儲器模型初探 233
9.2 示例1：尋找最小值 235
9.3 示例2：二進制搜索 239
9.3.1 生物信息學(xué)用例 239
9.3.2 運行時間分析 241
9.4 最優(yōu)搜索 243
9.5 示例3：合并K 個排序列表 246
9.5.1 合并時間/日期日志 246
9.5.2 外部存儲器模型是否過于簡單 250
9.6 下一章內(nèi)容 251
9.7 本章小結(jié) 251
第10 章 數(shù)據(jù)庫的數(shù)據(jù)結(jié)構(gòu)：B 樹、Bε 樹和LSM 樹 253
10.1 索引的工作原理 254
10.2 本章中的數(shù)據(jù)結(jié)構(gòu) 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 緩沖區(qū)機制· 273
10.5.3 插入和刪除 275
10.5.4 查找 276
10.5.5 成本分析 277
10.5.6 Bε 樹：數(shù)據(jù)結(jié)構(gòu)的范圍 278
10.5.7 用例：TokuDB 中的Bε 樹 279
10.5.8 輸入/輸出之道：欲速則不達 280
10.6 日志結(jié)構(gòu)合并樹(LSM 樹) 281
10.6.1 LSM 樹：工作原理 283
10.6.2 LSM 樹成本分析 285
10.6.3 用例：Cassandra 中的LSM 樹 286
10.7 本章小結(jié) 287
第11 章 外部存儲器排序 289
11.1 排序用例 290
11.1.1 機器人運動規(guī)劃 290
11.1.2 癌癥基因組學(xué) 291
11.2 外部存儲器排序的挑戰(zhàn)：示例 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 為什么外部存儲器合并排序是最優(yōu)的 306
11.6 結(jié)尾 308
11.7 本章小結(jié) 309
參考文獻 310