主存存取原理主存的组成主存（简称主存或内存）包括存取体、各种逻辑元件和控制电路。存储体由许多存储单元组成，每个存储单元包含若干个存储元素，每个存储元素可以存储一位二进制代码“0”或“1”。这样，一个存储单元可以存储一串二进制码，称为存储字，这串二进制码的位数称为存储字长，可以是8位，16位，或32位。连接主存和CPU的MAR（MemoryAddressRegister）是一个内存地址寄存器，用来存放要访问的存储单元的地址，它的位数对应存储单元的个数（如果MAR为10位，有210=1024个存储单元，记为1k）。MDR（MemoryDataRegister）是内存数据寄存器，用来存放从内存块的某个单元中取出的代码，或者存放在某个存储单元中的代码，它的位数等于存储字的长度。现代计算机普遍在CPU芯片中集成了MAR和MDR。主存的访问过程如果把存储体看成是一栋楼，那么每个存储单元就可以看成楼里的每个房间，每个存储单元可以看成是房间里的一张床，床是被占用的相当于“1”，没有人相当于“0”。每个房间都需要一个房间号，这样我们就可以方便的找到房间所在的位置。同样，每个存储单元都可以分配一个编号，称为存储单元的地址编号。主存储器的工作方式是根据存储单元的地址号来实现对存储字的每一位的存储（写）和取（读）。现代主存的结构和存取原理都比较复杂。这里抛开具体的区别，抽象出一个非常简单的访问模型来说明主存的工作原理。对主存的访问过程如下：当系统需要读主存时，CPU先将字的地址发送给MAR，通过地址总线发送给主存，然后发出读命令。主存收到读命令后，根据地址定位到指定的存储单元，然后将该存储单元的数据放到数据总线上，供其他部件读取。写入主存的过程类似。将一个信息字存入主存时，CPU首先将存字的主存单元的地址通过MAR发送到地址总线，并将信息字发送到MDR，再将字写入MDR.主存发出写命令，主存接收到写命令后，将数据总线上的信息写入对应地址总线所指示的主存单元。画外音：其实访问主存的过程并没有这么简单，还需要经过地址译码（逻辑地址->物理地址）等过程。磁盘访问原理我们知道索引本身也很大，不可能全部存储在内存中（根节点驻留在内存中），一般以文件的形式存储在磁盘上。那么问题来了，索引检索需要进行磁盘I/O操作。与内存不同，磁盘I/O有机械运动的成本，而且与内存访问相比，I/O访问的消耗高出几个数量级。圆盘的组成圆盘整体结构示意图：圆盘由大小相同、同轴的圆盘组成，圆盘可以转动（每个圆盘必须同步转动）。磁盘的一侧有磁头支撑。磁头支持固定一组磁头，每个磁头负责访问一个磁盘的内容。磁头不能旋转，但可以沿磁盘的径向移动（实际上是倾斜移动）。每个头也必须同时同轴，即从顶部看，所有头在任何时候都是重叠的。磁盘盘片示意图：盘片被分成一系列的同心环，同心环的中心就是盘片的中心，每个同心环称为一个磁道，所有半径相同的磁道组成一个圆柱体。磁道沿径向线被分成小段，每一段称为一个扇区，每个扇区是磁盘的最小存储单元。磁盘访问过程：当需要从磁盘读取数据时，系统会将数据的逻辑地址传递给磁盘，磁盘的控制电路根据寻址逻辑将逻辑地址转换为物理地址，即判断要读取的数据在哪个磁道上。,哪个部门。为了读取该扇区的数据，需要将磁头放在扇区上方。为了实现这一点：首先，必须找到柱面，即磁头需要移动以对准相应的磁道。这个过程称为寻道，所花费的时间称为寻道时间，然后将目标扇区旋转到磁头下，即磁盘旋转将目标扇区旋转到磁头下。这个过程所花费的时间称为轮转时间，因此一次磁盘访问请求（读/写）的完成过程包括三个动作：寻道（时间）：磁头移动并定位到指定磁道轮转延时（时间）：等待指定扇区从磁头开始向下旋转通过数据传输（时间）：磁盘与内存之间实际数据传输和磁盘预读的局部性原理由于存储介质的特性，磁盘本身是访问速度比主存慢很多，再加上机械运动的成本，磁盘的访问速度往往是主存的百万分之一，所以为了提高效率，应该尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都提前读取。即使只需要一个字节，磁盘也会从这个位置开始，依次向后读取一定长度的数据到内存中。其理论依据是计算机科学中著名的局部性原理：局部性原理：CPU在访问内存时，无论是访问指令还是访问数据，访问的存储单元都倾向于聚集在一个较小的连续区域中间。时间局部性：如果一个信息项正在被访问，它很可能在不久的将来再次被访问。空间局部性：将在不久的将来使用的信息可能在空间上与当前正在使用的信息相邻。由于磁盘顺序读取的效率很高（不需要寻道时间，旋转时间很少），预读可以提高具有局部性的程序的I/O效率。预读的长度一般是页的整数倍。页是计算机管理的内存的逻辑块。硬件和操作系统通常将主内存和磁盘存储区域划分为大小相等的连续块。每个存储块称为一个页（在许多操作系统中，一个页的大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发缺页异常。这时，系统会向磁盘发送一个读信号，磁盘会找到数据的起始位置，并不断地向后读取一页或几页。载入内存，然后异常返回，程序继续运行。数据库为什么选择B-/+Tree索引前面说过，SQL优化的一个重要原则就是减少磁盘I/O的次数，而磁盘I/O的次数也是评价SQL好坏的指标之一索引结构。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中的节点去掉了数据字段，所以可以有更大的出度，更好的性能；第二，因为所有的叶子节点组成一个有序链表，方便范围查询；所有的搜索最终都会到达叶子节点，从而保证了查询性能的稳定性。
