第Ⅰ部分基于哈希的草圖
第1 章 導(dǎo)論 3
1.1 示例 5
1.1.1 示例解決方法 6
1.1.2 本書(shū)給出的解決方法 8
1.2 本書(shū)的結(jié)構(gòu) 11
1.3 本書(shū)的不同之處及目標(biāo)讀者 12
1.4 為什么大規(guī)模數(shù)據(jù)對(duì)當(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 基于硬件來(lái)設(shè)計(jì)算法 16
1.6 本章小結(jié) 17
第2 章 哈希表和現(xiàn)代哈�；仡� 19
2.1 無(wú)處不在的哈希 20
2.2 數(shù)據(jù)結(jié)構(gòu)概述 22
2.3 現(xiàn)代系統(tǒng)中的使用場(chǎng)景 25
2.3.1 備份/存儲(chǔ)解決方案中的重復(fù)數(shù)據(jù)刪除 25
2.3.2 使用MOSS 和Rabin-Karp 指紋識(shí)別進(jìn)行剽竊檢測(cè) 26
2.4 有關(guān)O(1) 29
2.5 解決沖突：理論與實(shí)踐 30
2.6 使用場(chǎng)景：Python 的dict是如何實(shí)現(xiàn)的 33
2.7 MurmurHash 35
2.8 分布式系統(tǒng)的哈希表：一致性哈希 36
2.8.1 一個(gè)典型的哈希問(wèn)題 37
2.8.2 哈希環(huán) 38
2.8.3 查找 41
2.8.4 添加新節(jié)點(diǎn)/資源 41
2.8.5 刪除節(jié)點(diǎn) 44
2.8.6 一致性哈希場(chǎng)景：Chord 48
2.8.7 一致性哈希：編程練習(xí) 50
2.9 本章小結(jié) 50
第3 章 近似成員關(guān)系：Bloom 過(guò)濾器和商
過(guò)濾器 53
3.1 工作原理 56
3.1.1 插入 56
3.1.2 查找 57
3.2 用例 58
3.2.1 網(wǎng)絡(luò)中的Bloom 過(guò)濾器：Squid 58
3.2.2 Bitcoin 移動(dòng)應(yīng)用 59
3.3 一個(gè)簡(jiǎn)單的實(shí)現(xiàn) 60
3.4 設(shè)置Bloom過(guò)濾器 61
3.5 一點(diǎn)理論 66
3.6 Bloom 過(guò)濾器的調(diào)整和替代方案 69
3.7 商過(guò)濾器 70
3.7.1 商-余數(shù)法 71
3.7.2 了解元數(shù)據(jù)位 73
3.7.3 示例：插入商過(guò)濾器中 73
3.7.4 用于查找的Python代碼 76
3.7.5 調(diào)整大小與合并 79
3.7.6 誤報(bào)率和空間考慮 80
3.8 Bloom 過(guò)濾器和商過(guò)濾器的比較 80
3.9 本章小結(jié) 82
第4 章 頻率估計(jì)和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 個(gè)睡眠不安者 92
4.3.2 縮放單詞的分布相似度 96
4.4 count-min sketch 中的誤差與空間 99
4.5 count-min sketch 的簡(jiǎn)單實(shí)現(xiàn) 100
4.5.1 練習(xí) 101
4.5.2 公式所蘊(yùn)含的原理 102
4.6 使用count-min sketch進(jìn)行范圍查詢 103
4.6.1 二元區(qū)間 104
4.6.2 更新階段 105
4.6.3 估計(jì)階段 107
4.6.4 計(jì)算二元區(qū)間 108
4.7 本章小結(jié) 110
第5 章 基數(shù)估計(jì)和HyperLogLog 113
5.1 對(duì)數(shù)據(jù)庫(kù)中的不同項(xiàng)計(jì)數(shù) 114
5.2 HyperLogLog 增量設(shè)計(jì) 116
5.2.1 第一步：概率計(jì)數(shù) 117
5.2.2 隨機(jī)平均 119
5.2.3 LogLog 121
5.2.4 HyperLogLog：使用調(diào)和平均值進(jìn)行隨機(jī)平均 123
5.3 用例：使用HLL 捕捉蠕蟲(chóng) 126
5.4 一個(gè)小實(shí)驗(yàn) 128
5.5 用例：使用Hyper-LogLog 進(jìn)行聚合 132
5.6 本章小結(jié) 135
第Ⅱ部分實(shí)時(shí)分析第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 負(fù)載平衡和跟蹤網(wǎng)絡(luò)流量 149
6.2 數(shù)據(jù)流中的實(shí)際約束和概念 151
6.2.1 實(shí)時(shí) 151
6.2.2 小時(shí)間和小空間 152
6.2.3 概念轉(zhuǎn)變和概念漂移 152
6.2.4 滑動(dòng)窗口模型 153
6.3 抽樣和估計(jì) 155
6.3.1 有偏差抽樣策略 157
6.3.2 代表性樣本的估計(jì) 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 從滑動(dòng)窗口抽樣 182
7.2.1 鏈?zhǔn)匠闃? 182
7.2.2 優(yōu)先級(jí)抽樣 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 相對(duì)誤差 203
8.2.3 數(shù)據(jù)域中的相對(duì)誤差 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 從頭開(kāi)始構(gòu)建q-digest 216
8.4.2 合并q-digest 218
8.4.3 q-digest 中的誤差和空間注意事項(xiàng) 219
8.4.4 使用q-digest 進(jìn)行分位數(shù)查詢 220
8.5 模擬代碼和結(jié)果 221
8.6 本章小結(jié) 226
第Ⅲ部分?jǐn)?shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)和外部存儲(chǔ)器算法

第9 章 外部存儲(chǔ)器模型 231
9.1 外部存儲(chǔ)器模型初探 233
9.2 示例1：尋找最小值 235
9.3 示例2：二進(jìn)制搜索 239
9.3.1 生物信息學(xué)用例 239
9.3.2 運(yùn)行時(shí)間分析 241
9.4 最優(yōu)搜索 243
9.5 示例3：合并K 個(gè)排序列表 246
9.5.1 合并時(shí)間/日期日志 246
9.5.2 外部存儲(chǔ)器模型是否過(guò)于簡(jiǎn)單 250
9.6 下一章內(nèi)容 251
9.7 本章小結(jié) 251
第10 章 數(shù)據(jù)庫(kù)的數(shù)據(jù)結(jié)構(gòu)：B 樹(shù)、Bε 樹(shù)和LSM 樹(shù) 253
10.1 索引的工作原理 254
10.2 本章中的數(shù)據(jù)結(jié)構(gòu) 256
10.3 B 樹(shù) 258
10.3.1 B 樹(shù)平衡 259
10.3.2 查找 260
10.3.3 插入 261
10.3.4 刪除 263
10.3.5 B 樹(shù) 266
10.3.6 B 樹(shù)上的操作有何不同 268
10.3.7 用例：MySQL 等中的B 樹(shù) 268
10.4 為什么B 樹(shù)查找在外部存儲(chǔ)器中是最佳的 269
10.5 Bε 樹(shù) 272
10.5.1 Bε 樹(shù)：工作原理 273
10.5.2 緩沖區(qū)機(jī)制· 273
10.5.3 插入和刪除 275
10.5.4 查找 276
10.5.5 成本分析 277
10.5.6 Bε 樹(shù)：數(shù)據(jù)結(jié)構(gòu)的范圍 278
10.5.7 用例：TokuDB 中的Bε 樹(shù) 279
10.5.8 輸入/輸出之道：欲速則不達(dá) 280
10.6 日志結(jié)構(gòu)合并樹(shù)(LSM 樹(shù)) 281
10.6.1 LSM 樹(shù)：工作原理 283
10.6.2 LSM 樹(shù)成本分析 285
10.6.3 用例：Cassandra 中的LSM 樹(shù) 286
10.7 本章小結(jié) 287
第11 章 外部存儲(chǔ)器排序 289
11.1 排序用例 290
11.1.1 機(jī)器人運(yùn)動(dòng)規(guī)劃 290
11.1.2 癌癥基因組學(xué) 291
11.2 外部存儲(chǔ)器排序的挑戰(zhàn)：示例 293
11.3 外部存儲(chǔ)器合并排序 297
11.4 外部快速排序 300
11.4.1 外部存儲(chǔ)器雙向快速排序 301
11.4.2 外部存儲(chǔ)器多向快速排序 302
11.4.3 找到足夠的樞軸 303
11.4.4 找到足夠好的樞軸 304
11.4.5 將它們重新組合在一起 305
11.5 為什么外部存儲(chǔ)器合并排序是最優(yōu)的 306
11.6 結(jié)尾 308
11.7 本章小結(jié) 309
參考文獻(xiàn) 310