数据库索引不只一种实现方法，但是其中最具代表性，也是我们面试中遇到最多的无疑是B+树。

索引为什么选择B+树

数据量很大的查找，是不能直接放入内存的，而是需要什么数据就通过磁盘IO去获得。

红黑树，AVL树等二叉查找树虽然效率高，但是树的高度也大，每次访问结点都需要一次IO；而B树B+树这种多路查找树可以使得树的高度变小。

在最坏的情况下，一次IO就只能获得一个结点的值，所以在最坏的情况下，不管是红黑树还是AVL树、B树、B+树，他们对应的磁盘操作是树的高度。

索引为什么不选择B树

• B树只适合随机检索，而B+树同时支持随机检索和顺序检索；
• B+树空间利用率更高，可减少I/O次数，磁盘读写代价更低。一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗。B+树的内部结点并没有指向关键字具体信息的指针，只是作为索引使用，其内部结点比B树小，盘块能容纳的结点中关键字数量更多，一次性读入内存中可以查找的关键字也就越多，相对的，IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素；
• B+树的查询效率更加稳定。B树搜索有可能会在非叶子结点结束，越靠近根节点的记录查找时间越短，只要找到关键字即可确定记录的存在，其性能等价于在关键字全集内做一次二分查找。而在B+树中，顺序检索比较明显，随机检索时，任何关键字的查找都必须走一条从根节点到叶节点的路，所有关键字的查找路径长度相同，导致每一个关键字的查询效率相当。
• B-树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起，只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作。
• 增删文件（节点）时，效率更高。因为B+树的叶子节点包含所有关键字，并以有序的链表结构存储，这样可很好提高增删效率。