B+树作为数据库索引结构的优势对比

MySQL作为数据库，它的功能就是做数据存储和数据查找；使用B+树作为索引结构是为了实现高效的查找、插入和删除操作。

B+树的查找、插入、删除的复杂度都为 O(log n)，它是一个多叉树的结构，能兼顾各种操作的效率的数据结构。如果使用平衡二叉树或者红黑树，树的高度就会涨的很快，查询的次数就会变多了，不利于查找，磁盘的I/O次数就会变多。

范围查找很快，B+树的叶子节点是使用双向链表链接起来的，找到要查找的范围，顺序读取就可以了

扩展

我们可以用作查找、插入和删除的数据结构有：数组、链表、哈希表、树、堆、跳表、字典树…

数组

查找：有序数组使用二分查找复杂度为 O(log n)，如果是无序数组需要遍历，查找复杂度为 O(n)
插入和删除的复杂度，在最坏情况下都是 O(n)

链表

查找复杂度为 O(n)，因为每次都需要从头开始遍历
插入如果直接都在头部插入复杂度为 O(1)，需要有序的话复杂度为 O(n)；删除复杂度为 O(n)

哈希表

查找、插入和删除都是理想情况下为 O(1)，如果冲突较多会退化到 O(n)

为什么不用？

• 基于哈希函数进行索引的，不能做范围查找，部分查询
• 冲突较多各个操作会退化到 O(n)

二叉树（AVL树、红黑树、2-3树）

查找、插入和删除都是 O(log n)

为什么不用？

• 磁盘的存储效率不高，每个节点包含的数据太少，查找时会存在大量的寻址开销
• 因为这个只有二叉，在数据量很大的时候，树的高度会很大的影响各个操作的效率

B树

查找、插入和删除都是 O(log n)

为什么不用？

• B树的所有节点都可以存储数据，B+树只有叶子结点可以存储数据
• 在范围查找时，B树不如B+树的效率高
• B树在插入和删除的时候需要更多的节点更新操作，B+树插入和删除通常只在叶子节点上发生，操作相对简单，保持了高效率

跳表

查找、插入和删除都是 O(log n)

为什么不用？

• 跳表需要维护多级指针，占用磁盘额外空间，需要的磁盘查找次数更多，在内存处理中表现很好，但是磁盘效率不高
• 为了实现高效的查询，占用了更多的内存空间

看起来主要是磁盘I/O的效率的原因居多，B+树设计的对磁盘I/O很友好；比其他的数据结构，需要更少的磁盘I/O