实际的大规模存储中，在实现索引查询的背景下，树能存储的数据量是有限的，大数据量情况下导致树过深造成磁盘I/O读写过于频繁（磁盘构造有关），导致查询效率底下。那么减小树的深 度就成为有效的提高查询效率的手段。那么很自然一个想法就是多叉树结构。

磁盘上数据通过一个三维地址唯一标示：柱面号、盘面号、块号(磁道上的盘块)。

磁盘的读写需要经过三个步骤：

访问具体信息由三步时间组成：

查找时间(seek time) Ts：完成上面步骤一所需时间，代价最高，最大到0.1s左右。

传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间。

B-Tree、B+Tree是多路搜索树，查询任意一个节点，IO次数是恒定的，最多需要访问h个节点（h为树高）。

mysql巧妙地将一个节点的大小设置了一页的大小，每次磁盘读取一页的数据就能在一次IO 的情况下将整个节点的数据读出来。

mysql B-Tree一般高度不超过3，100阶的高度为3的B-Tree，可以存100100100=10^6的数据，基本上3次IO就可以完成索引。

因为红黑树是二叉树，存储大量数据的时候树的高度会非常大，会造成多次IO读取，性能很差。如上所述10^6的数据在红黑树中就不可能在3次IO内完成，因此红黑树不适合作为外存索引。

由此可以看出提高索引查询效率的关键在于减少磁盘的定位和IO次数，而减少磁盘IO关键在于降低树的高度。