内容简介

　　《数据库系统实现（第2版）》是斯坦福大学计算机科学专业数据库系列课程第二门课的教科书。书中对数据库系统实现原理进行了深入阐述，并具体讨论了数据库管理系统的三个主要成分——存储管理器、查询处理器和事务管理器的实现技术。此外，第2版充分反映了数据管理技术的新进展，对内容进行了扩充，除了在第1版中原有的“信息集成”一章（第10章）中加入了新的内容外，还增加了两个全新的章：“数据挖掘”（第11章）和“数据库系统与互联网”（第12章）。
　　《数据库系统实现（第2版）》适合作为高等院校计算机专业研究生的教材或本科生的教学参考书，也适合作为从事相关研究或开发工作的专业技术人员的高级参考资料。

经常书评

目录

出版者的话
译者序
译者简介
出版前言
第1章 DBMS系统概述
1.1 数据库系统的发展
1.1.1 早期的数据库管理系统
1.1.2 关系数据库系统
1.1.3 越来越小的系统
1.1.4 越来越大的系统
1.1.5 信息集成
1.2 数据库管理系统概述
1.2.1 数据定义语言命令
1.2.2 查询处理概述
1.2.3 主存和缓冲区管理器
1.2.4 事务处理
1.2.5 查询处理器
1.3 本书概述
1.4 数据库模型和语言回顾
1.4.1 关系模型回顾
1.4.2 SQL回顾
1.5 参考文献
第一部分数据库系统实现

第2章 辅助存储管理
2.1 存储器层次
2.1.1 存储器层次
2.1.2 在存储器层次间传送数据
2.1.3 易失和非易失存储器
2.1.4 虚拟存储器
2.1.5 习题
2.2 磁盘
2.2.1 磁盘结构
2.2.2 磁盘控制器
2.2.3 磁盘存取特性
2.2.4 习题
2.3 加速对辅助存储器的访问
2.3.1 计算的I/O模型
2.3.2 按柱面组织数据
2.3.3 使用多个磁盘
2.3.4 磁盘镜像
2.3.5 磁盘调度和电梯算法
2.3.6 预取和大规模缓冲
2.3.7 习题
2.4 磁盘故障
2.4.1 间断性故障
2.4.2 校验和
2.4.3 稳定存储
2.4.4 稳定存储的错误处理能力
2.4.5 从磁盘崩溃中恢复
2.4.6 作为冗余技术的镜像
2.4.7 奇偶块
2.4.8 一种改进：RAID5
2.4.9 多个盘崩溃时的处理
2.4.10 习题
2.5 组织磁盘上的数据
2.5.1 定长记录
2.5.2 定长记录在块中的放置
2.5.3 习题
2.6 块和记录地址的表示
2.6.1 客户机-服务器系统中的地址
2.6.2 逻辑地址和结构地址
2.6.3 指针混写
2.6.4 块返回磁盘
2.6.5 被钉住的记录和块
2.6.6 习题
2.7 变长数据和记录
2.7.1 具有变长字段的记录
2.7.2 具有重复字段的记录
2.7.3 可变格式的记录
2.7.4 不能装入一个块中的记录
2.7.5 BLOB
2.7.6 列存储
2.7.7 习题
2.8 记录的修改
2.8.1 插入
2.8.2 删除
2.8.3 修改
2.8.4 习题
2.9 小结
2.10 参考文献

第3章 索引结构
3.1 索引结构基础
3.1.1 顺序文件
3.1.2 稠密索引
3.1.3 稀疏索引
3.1.4 多级索引
3.1.5 辅助索引
3.1.6 辅助索引的运用
3.1.7 辅助索引中的间接
3.1.8 文档检索和倒排索引
3.1.9 习题
3.2 B-树
3.2.1 B-树的结构
3.2.2 B-树的应用
3.2.3 B-树的查找
3.2.4 范围查询
3.2.5 B-树的插入
3.2.6 B-树的删除
3.2.7 B-树的效率
3.2.8 习题
3.3 散列表
3.3.1 辅存散列表
3.3.2 散列表的插入
3.3.3 散列表的删除
3.3.4 散列表索引的效率
3.3.5 可扩展散列表
3.3.6 可扩展散列表的插入
3.3.7 线性散列表
3.3.8 线性散列表的插入
3.3.9 习题
3.4 多维索引
3.4.1 多维索引的应用
3.4.2 利用传统索引执行范围查询
3.4.3 利用传统索引执行最近邻查询
3.4.4 多维索引结构综述
3.5 多维数据的散列结构
3.5.1 网格文件
3.5.2 网格文件的查找
3.5.3 网格文件的插入
3.5.4 网格文件的性能
3.5.5 分段散列函数
3.5.6 网格文件和分段散列的比较
3.5.7 习题
3.6 多维数据的树结构
3.6.1 多键索引
3.6.2 多键索引的性能
3.6.3 kd-树
3.6.4 kd-树的操作
3.6.5 使kd-树适合辅助存储器
3.6.6 四叉树
3.6.7 R-树
3.6.8 R-树的操作
3.6.9 习题
3.7 位图索引
3.7.1 位图索引的动机
3.7.2 压缩位图
3.7.3 分段长度编码位向量的操作
3.7.4 位图索引的管理
3.7.5 习题
3.8 小结
3.9 参考文献

第4章 查询执行
4.1 物理查询计划操作符介绍
4.1.1 扫描表
4.1.2 扫描表时的排序
4.1.3 物理操作符计算模型
4.1.4 衡量代价的参数
4.1.5 扫描操作符的I/O代价
4.1.6 实现物理操作符的迭代器
4.2 一趟算法
4.2.1 一次单个元组操作的一趟算法
4.2.2 整个关系的一元操作的一趟算法
4.2.3&nb

试读

　　1.2.3 主存和缓冲区管理器
　　数据库中的数据通常驻留在辅助存储器中，在当今的计算机系统中，“辅助存储器”通常就是磁盘。然而，数据必须在主存储器中，才能对其进行有用的操作。存储管理器的任务是控制数据在磁盘上的放置和在磁盘与主存之间的移动。
　　在一个简单的数据库系统中，存储管理器和底层操作系统的文件系统没有什么不同。但是。为了提高效率，DBMS通常直接控制在磁盘上的存储，至少在一些情况下是这样的。存储管理器跟踪文件在磁盘上所处的位置，获得缓冲区管理器所要求的文件的磁盘块号。
　　缓冲区管理器负责将可利用的主存空间分割成缓冲区，缓冲区是与页面同等大小的区域，磁盘块的内容可以传送到缓冲区中。这样，所有需要从磁盘得到信息的DBMS成分都或直接或通过执行引擎与缓冲区和缓冲区管理器交互。
　　不同的DBMS成分所需要的信息的类型包括：
　　1.数据：数据库自身的内容。
　　2.元数据：描述数据库的结构及其约束的数据库模式。
　　3.日志记录：关于最近对数据库所做改变的信息，这些信息支持数据库的持久性。
　　4.统计信息：DBMS收集和存储的关于数据库中的各个关系或其他成分的大小、取值等信息。
　　5.索引：支持对数据进行高效存取的数据结构。
　　1.2.4 事务处理
　　正如前面所讲，通常将一个或多个数据库操作组成一组，称作事务，事务是必须被作为一个原子，外观上独立于其他事务执行的单位。而且，DBMS保证持久性，即已完成事务所做的工作决不会丢失。事务管理器从应用系统接收事务命令，从而得知什么时候事务开始，什么时候事务结束，以及应用系统的期望（例如，某些应用可能不希望具有原子性）。
　　事务处理器执行下列任务：
　　1.日志记录：为了保证持久性，对于数据库的每一个变化都在磁盘上记录日志。日志管理器遵循几种策略中的某一种进行工作，这些策略保证不管在什么时候系统发生故障或“崩溃”，恢复管理器都能查看关于数据库变化的日志，并将数据库恢复到某个一致的状态。开始时，日志管理器将日志写到缓冲区中，然后它与缓冲区管理器协调，保证在适当的时候将缓冲区写到磁盘中（磁盘中的数据不受系统崩溃的影响）。2.并发控制：事务的执行从表面上看必须是孤立的。但是在大多数系统中，实际上有许多事务在同时执行。因此，调度器（并发控制管理器）必须保证多个事务的一个个动作以一种适当的顺序执行，从而使得最终的结果与这些事务事实上一个执行完了再执行下一个的结果相同。典型的调度器通过在数据库的某些部分上维护若干个锁来进行它的工作。这些锁防止两个事务以造成不良后果的方式存取数据的相同部分。如图1.1 所示，锁通常存储在主存储器中的封锁表中。调度器禁止执行引擎访问数据库中被封锁的部分，从而对查询和其他数据库操作的执行发生影响。

前言/序言

　　随着计算机硬件、软件技术的飞速发展和计算机系统在各行各业的广泛应用，数据已经成为各种机构的宝贵资源，数据库系统对于当今科研部门、政府机关、企事业单位等来说都是至关重要的。而数据库系统中的核心软件是数据库管理系统（DBMS）。DBMS用于高效地创建和存储大量的数据，并对数据进行有效的管理、处理和维护，是数据库专家和技术人员数十年研究开发的结果，是当前最复杂的系统软件之一。要深入掌握数据库系统的原理和技术，进而从事数据库管理软件和工具的开发，必须学习和研究数据库管理系统实现技术。要深入了解数据库系统的内部结构，以开发出高效的数据库应用系统，也需要学习和研究数据库管理系统实现技术。
　　Hector GarciaMolina、Jeffrey DUllman和Jennifer Widom是斯坦福大学著名的计算机科学家，多年来他们在数据库系统领域中做了大量的开创性工作，由他们撰写的《数据库系统实现》一书是关于数据库系统实现方面内容最为全面的著述之一。我们于2000年将《数据库系统实现》的第1版译成中文，国内许多大学采用它作为研究生数据库课程的教材或主要教学参考书，收到了良好的效果。
　　现在我们又翻译了《数据库系统实现》第2版。第2版保持了第1版的总体风格，首先对数据库系统实现原理进行了深入阐述，并具体讨论了数据库管理系统的三个主要成分——存储管理器、查询处理器和事务管理器的实现技术。与第1版相比，第2版对于数据存储和索引结构的阐述进行了适当的压缩，分别将原来的两章合并为一章；另外，增加了一章“并行与分布式数据库”（第9章），其中包括了第1版中分散在查询处理和事务管理的相关章节中的内容，并增加了有关分布式查询执行的一些新内容，例如，map reduce并行架构、P2P数据库以及分布式散列的实现等。同时，第2版充分反映了数据管理技术的新进展，对内容进行了扩充，除了在第1版中原有的“信息集成”一章（第10章）中加入了新的内容外，还增加了两个全新的章：“数据挖掘”（第11章）和“数据库系统与互联网”（第12章）。“数据挖掘”一章中包含了关联规则与频繁项集挖掘技术，从一个非常大的数据库或Web页面集合中发现“相似”的项的“最小散列”和“局部敏感散列”等关键技术，以及高维空间中大规模数据的聚簇问题等。“数据库系统与互联网”一章中重点阐述了与互联网相关的两个方面的数据库技术：Web搜索引擎及其PageRank算法，流数据模型以及管理数据流形式的大量数据所需的技术。
　　我们认为这本书既适合作为高等院校计算机专业研究生的教材或本科生的教学参考书，又适合作为从事相关研究或开发工作的专业技术人员的高级参考资料。
　　杨冬青全面组织了本书的翻译，吴愈青、包小源、唐世渭在本书的翻译和审校中做了大量的工作。除此之外，参加翻译的还有闫秋玲、郑丽丽、蔡慧慧、马煜、张棋、陈巍、郭思祺、夏海峰、翁学天、郭少松、李树节。
　　限于译者水平，译文中难免有疏漏和错误，欢迎批评指正。