永久免费wap建站济南推广营销公司
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