前言

大数据的技术本质就是高性能，有了足够的性能，大数据分析才能实实在在地落地。

性能优化要在确定有限的硬件条件下实施，软件并不能改变硬件的速度，我们能做的是设计更低复杂度的算法，使实质的计算量降下去，自然也就能获得更高的运算性能。

有些大数据算法有较好的适应性，各种情况都能工作，但通常也会因为更保守而难以获得高性能。为了减少计算量，我们要仔细研究数据和任务的特征并加以利用，因地制宜地设计出合适的存储方案与计算方法。

本书的内容即是针对不同场景和目标讲述适用的存储方案和优化算法，程序员熟悉了这些基本算法的原理及应用前提后，灵活组合运用就可以得心应手地解决业务中的高性能问题了。了解这些算法和特征后，对于大数据产品的技术选型和理解也能有长足的进步。

本书的算法主要面向结构化数据计算，涉及查找、过滤、分组、排序、连接等运算，这些是大数据计算的基础内容，也是数据分析计算中最常见的任务。

本书不只是将历史上的算法简单罗列汇总，其中有不少算法和优化技术在业界中都是首次写到图书中。这里也不只在理论上讨论高性能算法，还会涉及在复杂度上并没有特别优势但工程实践上能起到提高性能效果的技术手段。

本书不是面向初学者的读物，对读者有一定的专业要求：

1） 掌握关系数据库和 SQL 的各种运算，书中将不再解释这些运算的含义

2） 了解相当于大学计算机专业的数据结构课程的知识，相关概念会直接引用

3） 了解算法复杂度分析的基础知识

4） 最好熟悉 C/C++ 或 Java 等编程语言、操作系统的内存管理机制以及基本局域网

有些算法的原理过程较为繁琐和艰难，应用程序员也可以不必掌握，只要理解算法的适应条件，再熟悉应用例程后也可以使用。

本书将使用 SPL 来编写应用例程，并直接用 SPL 的数据类型和语法来描述计算目标，这需要读者事先了解，有 SPL 知识的读者也容易把这些术语转换成其它程序语言的对应词汇。SPL 的基础概念和术语可以参考 SPL 程序设计。

SQL 是目前最常用的结构化数据运算语言，但它过于粗泛，无法应用本书中的大部分优化算法。而 Java、C/C++ 这些程序语言缺乏结构化数据运算必要的概念，连这些也要重新定义就会占用过多篇幅，而且它们虽然能实现并应用这些算法，但代码会相当长，会有过多精力消耗在细节上。

SPL 可能是目前业界仅有的既能够应用这些算法且不致于太过繁琐的程序语言，读者在了解这些算法机理后，也可以再用 Java、C/C++ 等程序语言自行实现，还能获得更好性能。

本书共将讲述了几十种结构化大数据的基础高性能算法或存储方案。我们已经在较多实际场景灵活应用过这些方法，使用 SPL 实现的算法，和传统关系数据库上的 SQL 相比，经常能获得几倍甚至上百倍的性能提升。

理论上讲，作为程序语言，SPL 并不会比 SQL 快更多。SPL 能够跑得更快的原因在于实施了 SQL 无法实施的高性能算法。如果一个计算任务，用 SQL 实现时已经使用了最优的算法，那么使用 SPL 重写也不会跑得更快。但 SQL 中难以实现的高性能算法实在太多了，只要代码有一定的复杂性，几乎一定能找到可以改变存储和算法而优化的点。我们实施过十几个场景中，每次都能找到可以改进的环节，这时候使用 SPL 重写就能有效的提高整体性能。当然，使用 C/C++ 或 Java 去编写也能获得更高性能，但开发效率又太低了。

需要再次指出的是，这里的每种算法都各有各自的适应场景，甚至有些算法之间具有一定的矛盾性而不能同时使用，这都需要根据现实情况来选用。我们也一直在强调要充分了解任务的目标和数据特征，再因地制宜地设计优化方案。而且，现实中的大数据计算问题，并不会简单地和这里讲的算法一一对应，而是一个很综合的任务，要基于这些基础算法再组合运用。所以更重要的是要学会分析方法。

因为重点是讲述优化方案的算法和工程原题，这里没有涉及完整的实例和测试。读者有兴趣可以到 SPL 论坛去寻找更多测试实例和代码。

目录

【性能优化】1.1 [内存查找] 二分法
【性能优化】1.2 [内存查找] 序号定位
【性能优化】1.3 [内存查找] 位置索引
【性能优化】1.4 [内存查找] 哈希索引
【性能优化】1.5 [内存查找] 多层序号定位
【性能优化】1.6 [内存查找] 内表索引

【性能优化】2.1 [外存数据集] 文本文件分段
【性能优化】2.2 [外存数据集] 集文件及倍增分段
【性能优化】2.3 [外存数据集] 数据类型
【性能优化】2.4 [外存数据集] 组表与列存
【性能优化】2.5 [外存数据集] 有序及数据追加
【性能优化】2.6 [外存数据集] 复组表
【性能优化】2.7 [外存数据集] 数据更新

【性能优化】3.1 [外存查找] 二分法
【性能优化】3.2 [外存查找] 哈希索引
【性能优化】3.3 [外存查找] 排序索引
【性能优化】3.4 [外存查找] 行存和带值索引
【性能优化】3.5 [外存查找] 索引预加载
【性能优化】3.6 [外存查找] 批量查找
【性能优化】3.7 [外存查找] 返回集合的查找
【性能优化】3.8 [外存查找] 多索引归并
【性能优化】3.9 [外存查找] 全文检索

【性能优化】4.1 [遍历技术] 游标过滤
【性能优化】4.2 [遍历技术] 遍历复用
【性能优化】4.3 [遍历技术] 并行遍历
【性能优化】4.4 [遍历技术] 数据库并行加载
【性能优化】4.5 [遍历技术] 多路游标
【性能优化】4.6 [遍历技术] 分组汇总
【性能优化】4.7 [遍历技术] 聚合理解
【性能优化】4.8 [遍历技术] 冗余分组键
【性能优化】4.9 [遍历技术] 列式计算

【性能优化】5.1 [有序遍历] 有序分组汇总
【性能优化】5.2 [有序遍历] DISTINCT 和 COUNT(DISTINCT)
【性能优化】5.3 [有序遍历] 有序分组子集
【性能优化】5.4 [有序遍历] 程序游标
【性能优化】5.5 [有序遍历] 前半序分组
【性能优化】5.6 [有序遍历] 后半序分组
【性能优化】5.7 [有序遍历] 序号分组与可控分段
【性能优化】5.8 [有序遍历] 索引排序

【性能优化】6.1 [外键关联] 外键地址化
【性能优化】6.2 [外键关联] 临时地址化
【性能优化】6.3 [外键关联] 外键序号化
【性能优化】6.4 [外键关联] 时间键
【性能优化】6.5 [外键关联] 内连接语法
【性能优化】6.6 [外键关联] 索引复用
【性能优化】6.7 [外键关联] 对位序列
【性能优化】6.8 [外键关联] 大维表查找
【性能优化】6.9 [外键关联] 单边分堆

【性能优化】7.1 [归并与连接] 有序归并
【性能优化】7.2 [归并与连接] 分段归并
【性能优化】7.3 [归并与连接] 关联定位
【性能优化】7.4 [归并与连接] 附表

【性能优化】8.1 [多维分析] 部分预汇总
【性能优化】8.2 [多维分析] 时间段预汇总
【性能优化】8.3 [多维分析] 冗余排序
【性能优化】8.4 [多维分析] 布尔维序列
【性能优化】8.5 [多维分析] 标签位维度
【性能优化】8.6 [多维分析] 内存标签异动

【性能优化】9.1 [集群] 计算与数据分布
【性能优化】9.2 [集群] 集群复组表
【性能优化】9.3 [集群] 复写维表
【性能优化】9.4 [集群] 分段维表
【性能优化】9.5 [集群] 冗余式容错
【性能优化】9.6 [集群] 备胎式容错
【性能优化】9.7 [集群] 多作业负载均衡