【性能优化】 前言及目录

 

前言

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

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

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

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

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

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

本书不是面向初学者的读本,对读者有一定的专业要求:

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

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

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

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

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

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

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

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

目录

【性能优化】1.1 [内存查找] 二分法

【性能优化】1.2 [内存查找] 序号定位

【性能优化】1.3 [内存查找] 位置索引

【性能优化】1.4 [内存查找] 哈希索引

【性能优化】1.5 [内存查找] 多层序号定位

【性能优化】2.1 [外存数据集] 文本文件分段

【性能优化】2.2 [外存数据集] 集文件及倍增分段

【性能优化】2.3 [外存数据集] 数据类型

【性能优化】2.4 [外存数据集] 组表与列存

【性能优化】2.5 [外存数据集] 有序及数据追加

【性能优化】2.6 [外存数据集] 数据更新及复组表

【性能优化】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 [遍历技术] 冗余分组键

【性能优化】5.1 [有序遍历] 有序分组汇总

【性能优化】5.2 [有序遍历] 有序分组子集

【性能优化】5.3 [有序遍历] 程序游标

【性能优化】5.4 [有序遍历] 前半序分组

【性能优化】5.5 [有序遍历] 后半序分组

【性能优化】5.6 [有序遍历] 序号分组与可控分段

【性能优化】5.7 [有序遍历] 索引排序

【性能优化】6.1 [外键关联] 外键地址化

【性能优化】6.2 [外键关联] 临时地址化

【性能优化】6.3 [外键关联] 外键序号化

【性能优化】6.4 [外键关联] 内连接语法

【性能优化】6.5 [外键关联] 索引复用

【性能优化】6.6 [外键关联] 对位序列

【性能优化】6.7 [外键关联] 大维表查找

【性能优化】6.8 [外键关联] 单边分堆

【性能优化】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 [集群] 多作业负载均衡

【性能优化】 后记