大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构，为什么B-Tree和B+Tree在被如此广泛用于索引？先从数据结构的角度来分析。
几种常见的树结构
二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced Binary Search Tree），红黑树(Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三都是二叉查找树， 查找时间复杂度O(log2N)与树的深度有关，降低深度自然也能提高查询效率。
面临的问题
实际的大规模存储中，在实现索引查询的背景下，树能存储的数据量是有限的，大数据量情况下导致树过深造成磁盘I/O读写过于频繁（磁盘构造有关），导致查询效率底下。那么减小树的深 度就成为有效的提高查询效率的手段。那么很自然一个想法就是多叉树结构。
磁盘的构造
磁盘上数据通过一个三维地址唯一标示：柱面号、盘面号、块号(磁道上的盘块)。
磁盘的读写需要经过三个步骤：
- 定位（查找）：移动臂根据柱面号使磁头移动到所需要的柱面
- 确定盘面：这时根据盘面号来确定指定盘面上的磁道
- 确定块号：将指定块号的磁道段移动至磁头下
访问具体信息由三步时间组成：
- 查找时间(seek time) Ts：完成上面步骤一所需时间，代价最高，最大到0.1s左右。
- 等待时间(latency time) Tl：上述三步耗时。
- 传输时间(transmission time) Tt: 数据通过系统总线传送到内存的时间。
B-Tree、B+Tree为什么适合做索引
- 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关键在于降低树的高度。