MySQL详解：索引的介绍和原理分析( 四 ) _MySQL详解

总结根据上面，二叉查找树，红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B+Tree作为索引结构（目前MySQL的MYISAM 和 INNODB 都是采用B+Tree作为索引结构），这是因为B+Tree索引的设计是以计算机磁盘存储结构为理论基础的。
索引以索引文件的形式存储在磁盘上，当采用B+Tree查找的时候，产生磁盘I/O消耗对性能的影响比其他方式小很多（评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度）。
换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数，而B+Tree无疑是较优的算法。