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

时间:2025-02-23 07:52:37

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