是什么影响了数据库索引选型？

上一篇文章我们介绍了索引背后的数据结构，这篇文章我们来介绍影响索引数据结构选型的因素——存储器存取。

主存存取原理

主存的构成

主存储器（简称主存或内存）包括存取体、各种逻辑部件及控制电路等。存储体由许多存储单元组成，每个存储单元又包含若干个存储元件，每个存储元件能寄存一位二进制代码“0”或“1”。这样，一个存储单元可以存储一串二进制代码，这串二进制代码称为存储字，这串二进制代码的位数称为存储字长，可以是8位、16位或者32位等。

主存与CPU的联系

画外音：

MAR（Memory Address Register）是存储器地址寄存器，用来存放欲访问的存储单元的地址，其位数对应存储单元的个数（若MAR为10位，则有210=1024个存储单元，记为1k）。

MDR（Memory Data Register）是存储器数据寄存器，用于存放从存储体某单元取出的代码或准备往某存储单元存入的代码，其位数与存储字长相等。

现代计算机一般将MAR和MDR集成在CPU芯片中。

主存的存取过程

如果把存储体看做是一栋大楼，那么每个存储单元可以看成这栋大楼里的每个房间，每个存储元可以看做房间里的一张床位，床位有人相当于“1”，无人相当于“0”。每个房间都需要一个房间号，便于我们找到房间的位置。同样，可以赋予每个存储单元一个编号，称为存储单元的地址号。

主存的工作方式就是按照存储单元的地址号来实现对存储字各位的存（写入）、取（读出）。

现代主存的结构和存取原理比较复杂，这里抛却具体差别，抽象出一个十分简单的存取模型来说明主存的工作原理。

主存的存取过程如下：

当系统需要读取主存时，首先由CPU将该字的地址送到MAR,经地址总线送至主存，然后发出读命令。主存接到读命令后，根据地址定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程类似，若要向主存存入一个信息字时，首先CPU将该字要存入的主存单元的地址经MAR送到地址总线，并将信息字送入MDR，然后向主存发出写命令，主存接到写命令后，便将数据总线上的信息写入到对应地址总线指出的主存单元中。

画外音：实际上主存存取的过程并没有这么简单，还需要经过经过地址译码（逻辑地址—>物理地址）等过程。

磁盘存取原理

我们知道，索引本身也很大，不可能全部存储在内存中（根节点常驻内存），一般以文件形式存储在磁盘上。那么问题来了，索引检索需要磁盘I/O操作。与内存不同，磁盘I/O存在机械运动耗费，相对于内存存取，I/O存取的消耗要高几个数量级。

磁盘的构成

磁盘的整体结构示意图：

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的。

磁盘盘片示意图：

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。

磁盘的存取过程：

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。

为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点：

1. 首先必须找到柱面，即磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间
2. 然后目标扇区旋转到磁头下，即磁盘旋转将目标扇区旋转到磁头下。这个过程耗费的时间叫做旋转时间

所以一次访盘请求（读/写）完成过程由三个动作组成：

1. 寻道（时间）：磁头移动定位到指定磁道
2. 旋转延迟（时间）：等待指定扇区从磁头下旋转经过
3. 数据传输（时间）：数据在磁盘与内存之间的实际传输

局部性原理与磁盘预读

由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百万分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：

局部性原理: CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。 时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。 空间局部性（Spatial Locality）：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页的大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

数据库为什么选用B-/+Tree索引

之前提到过，SQL优化的一个重要原则是减少磁盘I/O次数，磁盘I/O次数也是评价索引结构的优劣的指标之一。

B-Tree分析：

根据B-Tree的定义，可知检索一次最多需要访问h（B-Tree的高度）个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。但是逻辑上存储在一个页里并不代表物理上也存储在一个页里，为了达到这个目的，每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O，因为根节点会常驻内存。复杂度为O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。所以B-Tree作为索引结构效率是非常高的。这也是为什么数据库不选用红黑树作为索引（数据结构）的原因，一是因为红黑树的高度h要大的多；二是红黑树节点在物理上可能是单独存储的，无法利用局部性原理。复杂度为O(h)，效率明显比B-Tree差的多。

B+Tree分析：

上篇文章说过，B+Tree更适合索引。究其原因，一是因为B+Tree内节点去掉了data域，因此可以拥有更大的出度，拥有更好的性能；二是因为所有叶子节点形成有序链表，便于范围查询；所有的查找最终都会到叶子节点，从而保证了查询性能的稳定。