漫畫算法與數據結構 Algorithms and Data Structures for Massive Datasets

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

目 錄

第Ⅰ部分基於哈希的草圖

第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