从局部性原理与磁盘预读原理来了解索引机制
参考文章，链接如下：
https://blog.****.net/coolwriter/article/details/80346454
https://blog.****.net/u010727189/article/details/79399384
https://blog.****.net/alber_twhite/article/details/41039705
目录
计算机各模块处理速度：CPU >> Cache >>> 主内存 >>>> 磁盘
局部性原理
CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。
—— 百度百科
将计算机分为数个层次（不同计算机层次数据不同，此处仅为普通数据作为分析）：
-
寄存器 64位
-
一级缓存L1 4×64KB
-
二级缓存L2 4×256KB
-
三级缓存L3 8MB
-
内存 4GB
-
磁盘 1TB
可以发现这些层次一个比一个更大。
寄存器，既是CPU的工作台，也是存放计算数据的地方。
CPU要工作，它需要数据或者地址，从哪里来？先从一级缓存里面找，找不到就从二级缓存里面找，依次类推。假如CPU到磁盘才有，那么这个数据就会存入内存，再存入三级缓存、二级缓存、一级缓存，最后存入寄存器，CPU用它来计算了。
所以说，可以这么看， L1是寄存器的缓存，L2是L1的缓存，依次这样下去，下面一层是上面一层的缓存。
CPU的工作要高速，我们希望CPU需要的数据更多的就在L1里面，迅速找到。不希望更多的跑到下面内存乃至磁盘里面去找，这样会花更多的时间。所以当CPU用了一个数据，计算机会遇见性的存入其他等会儿CPU可能会用到的数据到L1、L2、L3内存，用到的可能性越大，就能存到越接近寄存器的层次。这也才是缓存的真正意义。那么，计算机怎样才能判断一个数据接下来可能被用到？
时间局部性（Temporal Locality）
时间局部性：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
// 这是可以理解的，用过的数据当然可能再次被用到。
空间局部性（Spatial Locality）
空间局部性：在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的。
// 正在使用的某个数据地址旁边的数据，当然也是很可能被用到的，比如某个数组、集合等等。
顺序局部性（Order Locality）
顺序局部性：在典型程序中，除转移类指令外，大部分指令是顺序进行的。顺序执行和非顺序执行的比例大致是5:1。此外，对大型数组访问也是顺序的。
指令的顺序执行、数组的连续存放等是产生顺序局部性的原因。
// 正在执行的某个指令以及还在排队等候处理的指令，大部分是按照顺序来执行的。
磁盘预读原理
内存比磁盘的读写速度要快很多，但内存容量要远小于磁盘，而数据、程序的执行要调入内存后才能执行，所以内存和磁盘要经常进行I/O操作，I/O操作是个费事的过程，虽然现代系统已经有了通道（I/O处理机）技术的支持，但这远远不够（CPU的处理速度远远大于磁盘I/O的速度）。
计算机各模块处理速度：CPU >> Cache >>> 主内存 >>>> 磁盘
磁盘示意图如下：
内存读取（简述）
内存读取，内存是由一系列的存储单元组成的，每个存储单元存储固定大小的数据，且有一个唯一地址。当需要读内存时，将地址信号放到地址总线上传给内存，内存解析信号并定位到存储单元，然后把该存储单元上的数据放到数据总线上，回传。
写内存时，系统将要写入的数据和单元地址分别放到数据总线和地址总线上，内存读取两个总线的内容，做相应的写操作。
内存存取效率，跟次数有关，先读取A数据还是后读取A数据不会影响存取效率。
磁盘读取（详细）
磁盘存取，磁盘I/O涉及机械操作。磁盘是由大小相同且同轴的圆形盘片组成，磁盘可以转动(各个磁盘须同时转动)。磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不动，磁盘转动，但磁臂可以前后动，用于读取不同磁道上的数据。磁道就是以盘片为中心划分出来的一系列同心环。磁道又划分为一个个小段，叫扇区，是磁盘的最小存储单元。
磁盘读取时，系统将数据逻辑地址传给磁盘，磁盘的控制电路会解析出物理地址（哪个磁道，哪个扇区），于是磁头需要前后移动到相应的磁道——寻道，消耗的时间叫——寻道时间，磁盘旋转将对应的扇区转到磁头下（磁头找到对应磁道的对应扇区），消耗的时间叫——旋转时间，这一系列操作是非常耗时。
为了尽量减少I/O操作，计算机系统一般采取预读的方式，预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
计算机系统是分页读取和存储的，一般一页为4KB（8个扇区，每个扇区125B，8*125B=4KB），每次读取和存取的最小单元为一页，而磁盘预读时通常会读取页的整倍数。根据文章上述的【局部性原理】①当一个数据被用到时，其附近的数据也通常会马上被使用。②程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），所以即使只需要读取一个字节，磁盘也会读取一页的数据。
至于磁盘分页，参考计算机操作系统的分页，分段存储管理——逻辑地址和物理地址被分为大小相同的页面，逻辑地址中叫页，物理地址中叫块。
为什么使用B-Tree/B+Tree
二叉查找树进化品种的红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-Tree/B+Tree作为索引结构。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
分析B-Tree/B+Tree检索一次最多需要访问节点：
h=
数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：
每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。
B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O（h）=O（logmN）。一般实际应用中，m是非常大的数字，通常超过100，因此h非常小（通常不超过3）。
综上所述，用B-Tree作为索引结构效率是非常高的。
而红黑树这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O（h），效率明显比B-Tree差很多。
举例说明
B-Tree：如果一次检索需要访问4个节点，数据库系统设计者利用磁盘预读原理，把节点的大小设计为一个页，那读取一个节点只需要一次I/O操作，完成这次检索操作，最多需要3次I/O(根节点常驻内存)。数据记录越小，每个节点存放的数据就越多，树的高度也就越小，I/O操作就少了，检索效率也就上去了。
B+Tree：非叶子节点只存key，大大滴减少了非叶子节点的大小，那么每个节点就可以存放更多的记录，树更矮了，I/O操作更少了。所以B+Tree拥有更好的性能。