索引为什么要用B+树？

 

1.文件很大，不可能全部存储在内存中，故要存储到磁盘上；

2.索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数；

3.局部性原理与磁盘预读，预读的长度一般为页(page)的整倍数，(在许多操作系统中，页的大小通常为4k)

4.数据库系统巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入，(由于节点中有两个数组，所以地址连续)。而红黑树这种结构，明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远，无法利用局部性。