三种常见的索引底层数据结构：分别是哈希表、有序数组和搜索树。
哈希表这种适用于等值查询的场景，比如 memcached 以及其它一些 NoSQL 引擎，不适合范围查询。
有序数组索引只适用于静态存储引擎，等值和范围查询性能好，但更新数据成本高。
N 叉树由于读写上的性能优点以及适配磁盘访问模式以及广泛应用在数据库引擎中。
扩展（以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘。其实，树的第二层也有很大概率在内存中，那么访问磁盘的平均次数就更少了。）