目录 1
第一章 并行数据库——高性能数据库发展的必由之路 1
1.1 数据库应用的新特点和新要求 1
1.1.1 数据类型的多样化和复杂化 1
1.1.2 数据模型的演变 2
1.1.3 数据库的智能性 2
1.1.4 数据操作的复杂性 3
1.1.5 高性能数据操作的紧迫性 3
1.2 并行处理为满足新的数据库应用带来生机 3
1.2.1 一个并行数据处理的例子 4
1.2.2 并行数据库作为高性能数据库的理由 6
1.3 要解决的问题 8
2.1.1 关系数据库系统 11
2.1 数据库管理系统 11
第二章 并行数据库技术的基本知识 11
2.1.2 查询处理 13
2.2 并行查询处理中的问题 15
2.2.1 并行处理的体系结构 15
2.2.2 并行性分类 17
2.2.3 并行性的度量 18
2.2.4 并行数据放置（Data Placement） 18
2.2.5 并行查询优化 19
2.2.6 数据偏斜（Data Skew） 20
第三章 并行数据库的数据存储技术 21
3.1 引言 21
3.2 若干基本概念和术语 21
3.3.1 Round-Robin存储方法 23
3.3.2 Hash存储方法 23
3.3 单维数据存储技术 23
3.3.3 Range存储方法 24
3.3.4 Hybrid-Range存储方法 24
3.4 多维数据存储方法 26
3.4.1 k-d-B-Tree方法 26
3.4.2 hB-Tree结构 28
3.4.3 X-Tree树结构 28
3.4.4 可变深度的Trie树结构 31
3.5 基于格文件方法的多维数据存储技术 34
3.5.1 DM/CMD算法 34
3.5.2 基于异或的算法 36
3.5.3 ECC算法 37
3.5.4 Hilbert曲线算法 39
3.5.5 启发式算法 41
3.6 基于频率、相似度的多维数据空间放置算法 44
3.6.1 多维数据空间的划分算法——FMDPA算法 45
3.6.2 多维数据超方体放置算法——SMDPA算法 50
3.6.3 算法性能分析 55
3.6.4 数据重组算法 62
第四章 并行数据库操作算法 66
4.1 并行关系排序操作算法 66
4.2 并行关系连接操作算法 73
4.2.1 基于嵌套循环的并行连接算法 74
4.2.2 基于排序的并行连接算法 76
4.2.3 基于散列的并行连接算法 77
4.3 数据库并行算法的加速技术 96
4.3.1 索引（指针）加速技术 96
4.3.2 位向量加速技术 97
4.4 操作系统对并行Join算法的影响 99
4.5.1 数据偏斜对并行连接算法的影响 103
4.5 数据偏斜及其处理技术 103
4.5.2 基于预处理技术的抗数据偏斜方法 104
4.5.3 基于共享虚存机制的抗数据偏斜方法 108
第五章 并行查询及其优化技术 112
5.1 并行查询的查询树优化模型 113
5.2 连接图与连接顺序选择 115
5.3 基于左深树的查询优化技术 116
5.3.1 基于左深树模型的执行规划 117
5.3.2 左深树的生成算法 118
5.3.3 左深树模型的分析 119
5.4 基于右深树的查询优化技术 119
5.4.1 基于右深树模型的执行规划 119
5.4.2 静态右深树调度技术 121
5.4.4 Hybrid-Hash调度技术 122
5.4.3 动态右深树调度技术 122
5.4.5 右深树查询模型的优点 124
5.4.6 右深树的生成 124
5.5 分段右深树查询优化技术 125
5.6 “之”字型查询树优化技术 129
5.7 基于丛生树的查询优化技术 129
5.7.1 基于丛生树模型的查询执行规划 129
5.7.2 丛生树生成算法 131
5.8 并行查询优化中的处理机分配技术 132
5.8.1 自底向上处理机分配技术 133
5.8.2 自顶向下处理机分配技术 136
5.9 并行查询优化处理器的设计 136
5.9.1 并行查询优化处理器的结构 136
5.9.2 并行查询的执行依赖图生成 138
5.9.3 并行查询执行调度程序 138
5.9.4 数据流并行执行的实现机制 140
5.9.5 一个并行查询执行的示例 142
第六章 并行数据库服务器系统 144
6.1 系统实现 144
6.2 一个简单的并行数据库系统 144
6.2.1 准备工作 144
6.2.2 实现模型和数据组织 145
6.2.3 并行算法实现举例 146
6.2.4 并行二元连接的实现 149
6.2.5 认识并行数据库系统 150
6.3 Gamma系统 152
6.3.1 系统硬件结构 152
6.3.2 Gamma系统的数据划分 152
6.3.3 系统进程结构 153
6.3.4 查询执行模型和算法 154
6.3.5 事务管理 156
6.3.6 失败管理 157
6.4 Bubba系统 158
6.4.1 系统设计目标 158
6.4.2 系统硬件结构 158
6.4.3 系统界面 160
6.4.4 分布式执行模型 161
6.4.5 系统进程结构 164
6.4.6 存储管理和锁机制 165
6.5 商用并行数据库系统 167
6.5.1 Oracle并行服务器（OPS） 167
6.5.2 DB2 UDB PE介绍 170
6.6 国内并行数据库系统 173
6.6.1 PBASE系统 173
6.6.2 PARO系统 175
参考文献 178