数据库物理层简介

在之前的课程中，我们主要介绍了数据库系统中“较高层次”的结构，例如关系模型、表的结构等逻辑或概念模型，这是数据库符合数据库最初创建的原因的。因为我们想让数据库的用户尽可能地只关注于如何满足和实现自己的需求，而不用考虑数据是如何在数据库中存储的或者如何被查询到的，这样“封装”的思想在程序员世界中经常可以见到。

但是了解一下数据库在物理层面是如何组织的，可以帮助我们对数据库管理系统有更深的了解。首先在这一节中，我们将向大家介绍一些常见的存储介质。

常见的物理存储介质

在计算机系统中，有很多种物理存储介质，它们的存取速度和价格各有不同，因此它们各自适用的场景也不同，常见的物理存储介质有以下几种：

• 缓存（cache）
  缓存是读写速度最快且单位花费最高的存储介质。一般来说，缓存的管理都是由操作系统进行的，在数据库中我们一般不涉及这类存储介质；

• 主存（main memory）
  主存中存储的是操作指令和相关操作数据，它会与缓存有直接的数据交换。一般来说主存储器的大小都不足以容纳整个数据库，并且断电后主存中的数据将会丢失；

• 闪存（flash memory）
  闪存也是计算机内存储器的一部分，与主存相比，它断电后数据不丢失。它读出数据的速度与主存相当，但写入数据较为缓慢，这是由于它在写入数据时需要事先擦除某个数据区块的内容，但是如果能妥善地管理数据块，它的写入速度还是非常可观的。我们通常用到的 USB 就是闪存的一种。

• 磁盘存储（magnetic disk storage）
  磁盘存储器是最常用的存储数据库数据的介质，通常情况下，数据库的全体数据都存储在磁盘存储器中，在使用数据库时，系统从磁盘存储器中将相应的数据放入主存中进行操作，最终从主存写回磁盘存储器。磁盘存储器的价格较低，存储速度中等，很适合存储较大量的数据。

• 光存储（optical storage）
  最常见的光存储器包括 CD、DVD 等，它们只能被写入一次，写入之后只能读取，因此也被称为 WORM-disk（write-once read-many disk）。

• 磁带存储（tape storage）
  在进行数据库备份或存储档案数据时，经常用到磁带存储器。它的价格十分低廉但存储容量很大，不容易损坏并且可以长时间保存。因此在存储卫星产生的数据、备份规模较大或保存时间较长的数据时，会用到磁带存储。

这几种存储器从上至下，读写速度越来越慢、存储容量越来越大、价格越来越便宜。目前看来，还没有既物美又价廉的存储介质，每种介质都有适合它发挥能量的场景。

练习

image.png

数据是如何被存储的

定长记录的两个问题

不定长记录

文件组织方式

索引存在的意义

稠密索引

很明显，在检索记录的时候，使用稠密索引可以更快的定位到目标记录，但是稀疏索引可以节省占用的空间，并且减少由于维护和操作指针带来的开销。在实际的数据库中，我们必须综合考虑效率、占用空间和开销，争取达到某个平衡。通常采用的做法是，根据每次能被内存读入的数据块大小设置稀疏索引，每一个数据块对应一个索引项，这样可以很好地节省空间。等到占用空间并不大的数据块读入到读写速度较快的内存之中，就可以采取遍历记录的方式进行查找，这样做的效率是很可观的。

但是这样做就足够了吗？这可不一定。

多级索引

多级索引在数据库系统中应用十分广泛，它是一种非常理想的索引方式，在下一节中我们将为大家介绍实际数据库中常常采用的一种多级索引结构 B+ 树索引。不过我们先做一道题巩固一下今天所学的知识。

练习

什么是 B+ 树

顺序索引的一个致命缺点就是随着数据量的增加，在索引中搜索的效率不断下降。虽然效率的下降速度可以通过重新组织文件的方式有所延缓，但是高频率地进行文件组织更新也是我们不愿意看到的，它会耗费大量的时间和内存。

B+ 树索引是一种可以保证索引效率的结构，不管数据库中添加或删除多少数据，查询的效率是稳定的。这是因为它是一种 平衡树（balanced tree），从根节点到叶子节点的每一条路径的长度是一样的。它的每个非叶子节点都有 n/2 到 n 的子节点，其中n在每一棵平衡树中为一个确定的值。

从本质上讲，B+ 树仍然是一种多级索引，但是它的结构不同于顺序的多级索引。下图是一个 n = 5 的 B+ 树索引结构。

在 B+ 树中，非叶子结点上存储着子树中最大或最小的关键字，这样一来所有的叶子节点都是按照从小到大或从大到小的顺序排列的。如果将每一个非叶子节点的子树顺序交换，相应的，叶子节点的排列顺序也要颠倒。

练习

为啥用哈希

哈希函数

哈希桶的溢出

哈希索引