### 局部性原理 那么为什么数据库系统普遍使用B+树作为索引结构，而不选例如红黑树其他结构呢？首先要先来介绍下局部性原理和磁盘预读的概念。 一般来说，索引本身较大，不会全部存储在内存中，会以**索引文件**的形式存储在磁盘上。所以索引查找数据过程中就会产生磁盘IO操作，而磁盘IO相对于内存存取非常缓慢，因此索引结构要尽量**减少磁盘IO的存取次数**。 为了减少磁盘IO，磁盘往往会进行数据**预读**，会从某位置开始，预先向后读取一定长度的数据放入内存，即**局部性原理**。因为磁盘顺序读取的效率较高，不需要寻道时间，因此可以提高IO效率。 预读长度一般为页的整数倍，主存和磁盘以**页**作为单位交换数据。**当需要读取的数据不在内存时，触发缺页中断**，系统会向磁盘发出读取磁盘数据的请求，磁盘找到数据的起始位置并向后连续读取一页或几页数据载入内存，然后中断返回，系统继续运行。而一般数据库系统设计时会将B+树节点的大小设置为**一页**，这样每个节点的载入只需要一次IO