分布式数据库系统：大数据时代新型数据库技术 第3版

本书主要介绍分布式数据库系统和大数据库系统的基本理论与实现技术。全书共13章，第1～10章重点介绍经典的分布式数据库系统的基本理论和关键技术、当前流行的商品化数据库系统的分布式数据管理机制，以及大数据库管理的关键技术和流行的大数据库系统。第11～13章介绍当下流行的区块链分布式数据管理技术、AI赋能的数据管理技术以及分布式数据库的发展前瞻。<br />本书理论与实践相结合，可作为计算机及相关专业高年级本科生和研究生的教材，也可供数据库相关技术人员参考使用。

于戈，博士，东北大学计算机科学与工程学院教授、博士生导师，CCF会士。现任中国计算机学会信息系统专业委员会主任。曾任国务院学科评议组成员、国家自然科学基金委专家评审组成员、中国计算机学会数据库专业委员会副主任。获得国家教学成果奖1项、省教学成果奖3项，以及省部级科学技术奖10项。<br /><br />申德荣，博士，东北大学计算机科学与工程学院教授、博士生导师。现任中国计算机学会信息系统专业委员会执行委员，中国计算机学会数据库专业委员会执行委员。获辽宁省研究生教学成果奖1项，获沈阳市自然科学成果奖1项，获省部级科学技术奖3项。<br />

目　　录<br />前言<br />第1章　分布式数据库系统概论　1<br />1.1　引言及准备知识　1<br />1.1.1　基本概念　1<br />1.1.2　基础知识　4<br />1.2　分布式数据库系统的基本概念　5<br />1.2.1　节点/场地　5<br />1.2.2　分布式数据库　5<br />1.2.3　分布式数据库管理系统　6<br />1.2.4　分布式数据库系统应用<br />　举例　6<br />1.2.5　分布式数据库的特性　7<br />1.3　分布式数据库系统的作用和特点　9<br />1.3.1　作用　9<br />1.3.2　特点　9<br />1.4　分布式数据库系统中的关键<br />　技术　10<br />1.4.1　关键技术　10<br />1.4.2　典型的分布式数据库原型<br />　系统简介　11<br />1.5　大数据应用与分布式大数据库<br />　技术　12<br />1.5.1　大数据的类型和应用　12<br />1.5.2　大数据的特点　15<br />1.5.3　大数据处理过程　15<br />1.5.4　大数据管理新模式　16<br />1.5.5　分布式大数据库系统及<br />　关键技术　18<br />1.6　本章小结　21<br />习题　21<br />参考文献　22<br />第2章　分布式数据库系统的<br />　体系结构　25<br />2.1　DDBS的物理结构和逻辑结构　26<br />2.2　DDBS的体系结构　26<br />2.2.1　基于客户/服务器结构的<br />　体系结构　27<br />2.2.2　基于“中间件”的客户/<br />　服务器结构　28<br />2.3　DDBS的模式结构　30<br />2.4　DDBS的组件结构　32<br />2.5　多数据库集成系统　33<br />2.5.1　数据库集成　33<br />2.5.2　多数据库系统　35<br />2.6　DDBS的分类　38<br />2.6.1　三个基本特性　38<br />2.6.2　DDBS的分类图　39<br />2.7　元数据的管理　40<br />2.7.1　数据字典的主要内容和<br />　用途　40<br />2.7.2　数据字典的组织　40<br />2.8　Oracle系统体系结构介绍　41<br />2.8.1　Oracle系统体系结构　41<br />2.8.2　Oracle中实现分布式功能的<br />　组件　42<br />2.8.3　Oracle分布式数据库架构<br />　案例　44<br />2.9　分布式大数据库的系统体系<br />　结构　46<br />2.10　分布式大数据库系统案例　47<br />2.10.1　HBase　47<br />2.10.2　Spanner　49<br />2.10.3　OceanBase　51<br />2.11　本章小结　53<br />习题　53<br />参考文献　53<br />第3章　分布式数据库的设计　56<br />3.1　设计策略　56<br />3.1.1　Top-Down设计过程　56<br />3.1.2　Bottom-Up设计过程　57<br />3.2　分片的定义和作用　57<br />3.2.1　分片的定义　58<br />3.2.2　分片的作用　58<br />3.2.3　分片设计过程　59<br />3.2.4　分片的原则　59<br />3.2.5　分片的种类　60<br />3.2.6　分布透明性　60<br />3.3　水平分片的设计　60<br />3.3.1　定义　60<br />3.3.2　水平分片的操作　63<br />3.3.3　水平分片的设计　63<br />3.3.4　正确性检验　65<br />3.4　垂直分片的设计　66<br />3.4.1　定义　66<br />3.4.2　垂直分片的操作　67<br />3.4.3　垂直分片的设计　67<br />3.4.4　正确性检验　67<br />3.5　混合分片的设计　68<br />3.6　分片的表示方法　69<br />3.6.1　图形表示法　69<br />3.6.2　分片树表示方法　69<br />3.7　分配设计　70<br />3.7.1　分配类型　70<br />3.7.2　分配设计原则　72<br />3.7.3　分配模型　73<br />3.8　数据复制技术　74<br />3.8.1　数据复制的优势　74<br />3.8.2　数据复制的分类　75<br />3.8.3　复制的常用方法　75<br />3.9　Oracle数据库的数据分布设计<br />　案例　76<br />3.9.1　基于Oracle数据库链的<br />　数据分布设计　76<br />3.9.2　Oracle集中式数据库的<br />　数据分区技术　80<br />3.9.3　基于Oracle分片技术的<br />　分布式数据库案例　82<br />3.10　大数据库的分布设计　86<br />3.10.1　大数据模型　86<br />3.10.2　数据分区策略　93<br />3.11　典型的大数据分布设计案例　97<br />3.11.1　HBase　97<br />3.11.2　Spanner　102<br />3.11.3　OceanBase　105<br />3.12　本章小结　110<br />习题　110<br />参考文献　111<br />第4章　分布式数据存储　114<br />4.1　大数据分布式存储类型　114<br />4.2　分布式文件系统　116<br />4.2.1　HDFS简介　116<br />4.2.2　HDFS的关系数据存储<br />　结构　119<br />4.2.3　基本的SSTable数据存储<br />　结构　125<br />4.2.4　LSM-Tree存储结构　127<br />4.3　分布式对象存储技术　130<br />4.3.1　三种主流的网络存储<br />　结构　131<br />4.3.2　对象存储系统的体系<br />　结构　131<br />4.3.3　Ceph　134<br />4.3.4　Swift　137<br />4.3.5　主流分布式存储技术的<br />　比较　141<br />4.4　分布式索引结构　142<br />4.4.1　布隆过滤器　142<br />4.4.2　键值二级索引　145<br />4.4.3　跳跃表　148<br />4.4.4　分区数据上的索引结构　149<br />4.5　分布式缓存　151<br />4.5.1　分布式缓存概述　152<br />4.5.2　分布式缓存的体系结构　153<br />4.5.3　典型的分布式缓存系统　154<br />4.5.4　分布式缓存与存储引擎的<br />　结合使用　160<br />4.6　Oracle数据库的存储结构　161<br />4.6.1　Oracle数据库的物理存储<br />　结构　162<br />4.6.2　Oracle数据库的逻辑存储<br />　结构　163<br />4.7　大数据库分布存储案例　164<br />4.7.1　HBase　164<br />4.7.2　Spanner　168<br />4.7.3　OceanBase　171<br />4.8　本章小结　177<br />习题　178<br />参考文献　179<br />第5章　分布式查询处理<br />　与优化　181<br />5.1　查询处理基础　181<br />5.1.1　查询处理目标　181<br />5.1.2　查询优化的意义　183<br />5.1.3　查询优化的基本概念　186<br />5.1.4　查询优化的过程　187<br />5.2　查询处理器　189<br />5.2.1　查询处理器的特性　190<br />5.2.2　查询处理层次　192<br />5.3　查询分解　194<br />5.3.1　规范化　194<br />5.3.2　分析　195<br />5.3.3　约简　196<br />5.3.4　查询重写　197<br />5.4　数据局部化　200<br />5.5　片段查询的优化　202<br />5.6　Oracle查询计划案例　205<br />5.7　大数据库的查询处理及优化　207<br />5.7.1　NoSQL数据库的查询<br />　处理方法　207<br />5.7.2　基于MapReduce的查询<br />　处理　209<br />5.7.3　基于Hadoop的查询处理　214<br />5.7.4　基于Spark的数据分析<br />　处理　217<br />5.8　大数据库查询处理与优化案例　221<br />5.8.1　HBase　221<br />5.8.2　Spanner　222<br />5.8.3　OceanBase　227<br />5.9　本章小结　235<br />习题　235<br />参考文献　236<br />第6章　查询存取优化　238<br />6.1　基本概念　239<br />6.1.1　分布查询的执行与处理　239<br />6.1.2　查询存取优化的内容　240<br />6.2　存取优化的理论基础　242<br />6.2.1　查询代价模型　242<br />6.2.2　数据库的特征参数和<br />　统计信息　244<br />6.2.3　关系运算的特征参数　246<br />6.3　基于半连接的优化方法　255<br />6.3.1　半连接操作及相关规则　255<br />6.3.2　半连接运算的作用　256<br />6.3.3　使用半连接算法的通信<br />　代价估计　257<br />6.3.4　半连接算法优化原理　258<br />6.4　基于枚举法的优化技术　259<br />6.4.1　嵌套循环连接算法　259<br />6.4.2　基于排序的连接算法　262<br />6.4.3　哈希连接算法　264<br />6.4.4　基于索引的连接算法　264<br />6.4.5　连接关系的传输方法　265<br />6.5　集中式系统中的查询优化算法　265<br />6.5.1　INGRES　265<br />6.5.2　System R 方法　269<br />6.5.3　考虑代价的动态规划<br />　方法　270<br />6.5.4　PostgreSQL的遗传算法　273<br />6.6　分布式数据库系统中的查询<br />　优化算法　275<br />6.6.1　分布式INGRES方法　275<br />6.6.2　System R*方法　281<br />6.6.3　SDD-1方法　282<br />6.7　Oracle分布式查询优化案例　292<br />6.7.1　基于数据链的Oracle<br />　分布式查询优化　292<br />6.7.2　Oracle分片数据库查询<br />　优化　295<br />6.8　面向大数据的存取优化方法　299<br />6.8.1　大数据库的查询存取<br />　框架　299<br />6.8.2　基于索引的大数据库查询<br />　存取优化方法　300<br />6.8.3　基于并行的大数据库查询<br />　存取执行计划　304<br />6.9　大数据库系统的查询存取优化<br />　案例　306<br />6.9.1　HBase　 307<br />6.9.2　Spanner　308<br />6.9.3　OceanBase　318<br />6.10　本章小结　326<br />习题　326<br />参考文献　329<br />第7章　分布式事务管理　331<br />7.1　事务的基本概念　331<br />7.1.1　事务的定义　331<br />7.1.2　事务的基本性质　333<br />7.1.3　事务的种类　335<br />7.2　分布式事务　336<br />7.2.1　分布式事务的定义　336<br />7.2.2　分布式事务的实现模型　336<br />7.2.3　分布式事务管理的目标　339<br />7.3　分布式事务的提交协议　340<br />7.3.1　协调者和参与者　340<br />7.3.2　两段提交协议的基本<br />　思想　341<br />7.3.3　两段提交协议的基本<br />　流程　342<br />7.4　分布式事务管理的实现　343<br />7.4.1　LTM与DTM　344<br />7.4.2　分布式事务执行的控制<br />　模型　344<br />7.4.3　分布式事务管理的实现<br />　模型　346<br />7.5　两段提交协议的实现方法　348<br />7.5.1　集中式方法　348<br />7.5.2　分布式方法　349<br />7.5.3　分层式方法　349<br />7.5.4　线性方法　350<br />7.6　非阻塞分布式事务提交协议　351<br />7.6.1　三段提交协议的基本<br />　思想　352<br />7.6.2　三段提交协议执行的<br />　基本流程　354<br />7.7　Oracle分布事务管理案例　355<br />7.8　大数据库的事务管理　359<br />7.8.1　大数据库的事务管理<br />　问题　359<br />7.8.2　大数据库系统设计的理论<br />　基础　360<br />7.8.3　弱事务型与强事务型<br />　大数据库　362<br />7.8.4　大数据库中的事务特性　364<br />7.8.5　大数据库的事务实现<br />　方法　367<br />7.9　大数据库的分布式事务管理<br />　案例　374<br />7.9.1　HBase　374<br />7.9.2　Spanner　377<br />7.9.3　OceanBase　379<br />7.10　本章小结　382<br />习题　383<br />参考文献　384<br />第8章　分布式恢复管理　386<br />8.1　分布式恢复概述　386<br />8.1.1　故障类型　386<br />8.1.2　恢复模型　389<br />8.2　集中式数据库的故障恢复　392<br />8.2.1　局部恢复系统的体系<br />　结构　392<br />8.2.2　数据更新策略　392<br />8.3　分布式事务的故障恢复　393<br />8.3.1　两段提交协议对故障的<br />　恢复　393<br />8.3.2　三段提交协议对故障的<br />　恢复　396<br />8.4　分布式可靠性协议　399<br />8.4.1　可靠性和可用性　399<br />8.4.2　分布式可靠性协议的<br />　组成　402<br />8.4.3　两段提交协议的终结<br />　协议　402<br />8.4.4　两段提交协议的演变　405<br />8.4.5　三段提交协议的终结<br />　协议　405<br />8.4.6　三段提交协议的演变　407<br />8.5　Oracle分布式数据库系统故障<br />　恢复案例　409<br />8.6　大数据库的恢复管理　412<br />8.6.1　大数据库的恢复管理<br />　问题　412<br />8.6.2　大数据库系统中的故障<br />　类型　413<br />8.6.3　大数据库系统的故障检测<br />　技术　414<br />8.6.4　基于事务的大数据库容错<br />　技术　416<br />8.6.5　基于冗余的大数据库容错<br />　技术　416<br />8.6.6　针对不同更新事务的恢复<br />　方法　421<br />8.7　大数据库的分布式恢复管理<br />　案例　423<br />8.7.1　HBase　423<br />8.7.2　Spanner　425<br />8.7.3　OceanBase　428<br />8.8　本章小结　431<br />习题　431<br />参考文献　432<br />第9章　分布式并发控制　435<br />9.1　分布式并发控制的基本概念　435<br />9.1.1　并发控制的问题　435<br />9.1.2　并发控制的定义　437<br />9.2　并发控制理论基础　437<br />9.2.1　事务执行过程的形式化<br />　描述　437<br />9.2.2　集中库的可串行化<br />　问题　438<br />9.2.3　分布式事务的可串行化<br />　问题　439<br />9.3　基于锁的并发控制方法　440<br />9.3.1　锁的类型和相容性　440<br />9.3.2　封锁规则　440<br />9.3.3　锁的粒度　441<br />9.4　两段锁协议　441<br />9.4.1　基本的两段锁协议　441<br />9.4.2　严格的两段锁协议　443<br />9.4.3　可串行性证明　444<br />9.5　 分布式数据库并发控制方法　444<br />9.5.1　基于锁的并发控制方法的<br />　实现　444<br />9.5.2　基于时间戳的并发控制<br />　算法　447<br />9.5.3　乐观的并发控制算法　450<br />9.6　分布式死锁管理　452<br />9.6.1　死锁等待图　452<br />9.6.2　死锁的检测　453<br />9.6.3　死锁的预防和避免　455<br />9.7　Oracle数据库并发控制案例　456<br />9.7.1　Oracle中的锁机制　456<br />9.7.2　Oracle中的并发控制　457<br />9.8　大数据库并发控制技术　458<br />9.8.1　事务读写模式扩展　458<br />9.8.2　封锁机制扩展　459<br />9.8.3　基于多版本并发控制<br />　扩展　462<br />9.9　大数据库的分布式并发控制<br />　案例　464<br />9.9.1　HBase　464<br />9.9.2　Spanner　466<br />9.9.3　OceanBase　470<br />9.10　本章小结　474<br />习题　474<br />参考文献　476<br />第10章　数据复制与一致性　478<br />10.1　数据复制的作用　478<br />10.2　数据复制一致性模型　479<br />10.3　分布式数据库复制策略　480<br />10.3.1　数据复制的执行方式　480<br />10.3.2　数据复制的实现方法　481<br />10.3.3　数据复制的体系结构　482<br />10.4　数据复制协议　483<br />10.4.1　主从复制协议　483<br />10.4.2　对等复制协议　487<br />10.5　大数据库一致性协议　488<br />10.5.1　Paxos协议　488<br />10.5.2　反熵协议　489<br />10.5.3　NWR协议　491<br />10.5.4　向量时钟技术　492<br />10.6　大数据库复制一致性管理　494<br />10.6.1　基于Paxos的复制管理<br />　技术　494<br />10.6.2　基于反熵的复制管理<br />　技术　498<br />10.6.3　基于NWR的复制管理<br />　技术　499<br />10.6.4　基于向量时钟的复制<br />　管理技术　501<br />10.6.5　ZooKeeper的ZAB<br />　协议　502<br />10.7　Oracle数据库复制技术　504<br />10.8　大数据库复制与一致性管理<br />　案例　507<br />10.8.1　HBase　507<br />10.8.2　Spanner　511<br />10.8.3　OceanBase　512<br />10.9　本章小结　515<br />习题　515<br />参考文献　515<br />第11章　区块链分布式数据<br />　管理　517<br />11.1　区块链系统概述　517<br />11.1.1　区块链系统的起源　517<br />11.1.2　区块链系统与传统数据库<br />　系统的对比　519<br />11.1.3　区块链系统的分类　520<br />11.1.4　区块链系统的体系结构　523<br />11.2　区块链的主要数据结构　525<br />11.2.1　区块链拓扑结构　525<br />11.2.2　区块数据存储结构　526<br />11.3　区块链的数据存储　529<br />11.3.1　区块链数据存储方法　529<br />11.3.2　区块链系统扩展存储<br />　方法　532<br />11.4　区块链系统的数据管理　533<br />11.4.1　区块链的存取优化　533<br />11.4.2　区块链系统的查询<br />　处理　534<br />11.5　区块链系统的事务管理　535<br />11.5.1　共识机制　535<br />11.5.2　智能合约　537<br />11.5.3　分布式事务处理　537<br />11.6　本章小结　539<br />习题　539<br />参考文献　539<br />第12章　AI赋能的数据管理　542<br />12.1　人工智能相关技术简介　542<br />12.1.1　决策树　542<br />12.1.2　聚类　543<br />12.1.3　人工神经网络　543<br />12.1.4　强化学习　544<br />12.2　数据分区　545<br />12.3　索引构建　546<br />12.4　查询优化　549<br />12.4.1　代价模型　549<br />12.4.2　基数估计　551<br />12.4.3　连接优化　553<br />12.5　负载管理与负载预测　556<br />12.5.1　负载管理　556<br />12.5.2　负载预测　558<br />12.6　配置参数调优　559<br />12.7　AI赋能的自治数据库系统　561<br />12.8　本章小结　562<br />习题　562<br />参考文献　562<br />第13章　分布式数据库系统<br />　发展与前瞻　567<br />13.1　云原生数据库系统　567<br />13.1.1　Aurora数据库系统　568<br />13.1.2　PolarDB数据库系统　572<br />13.2　事务与分析混合处理数据库<br />　系统　575<br />13.2.1　SAP HANA系统　576<br />13.2.2　TiDB数据库系统　580<br />13.3　其他类型的分布式大数据库<br />　管理系统　583<br />13.3.1　NoSQL分布式大数据库<br />　系统　583<br />13.3.2　面向OLTP的分布式<br />　大数据库系统　584<br />13.3.3　跨异构处理系统的分布式<br />　大数据库系统　585<br />13.4　数据库及大数据管理系统的<br />　发展方向　585<br />13.4.1　数据科学　586<br />13.4.2　数据治理　586<br />13.4.3　云数据库服务　587<br />13.4.4　数据库引擎　589<br />13.4.5　新型数据库应用　590<br />13.5　本章小结　592<br />习题　592<br />参考文献　592