• B+ 树的简单认识


    B+ 树的概念

    基本概念

    B+ 树是 B 树的一种变体,从某个程度上看,B+ 树可以认定是 B 树的升级版。

    在 B+ 树中,关键字只存储在叶子结点,非叶子结点存储的是叶子结点所存储关键字的部分拷贝,所有的叶子结点也都在相同的高度,叶子结点本身按关键字大小从小到大链接。

    因此,相对于 B 树而言,B+ 树更充分地利用了结点的空间,让查询速度更加稳定,其速度完全接近于二分查找。

    B+ 树结构

    特性

    B+ 树拥有 B 树的大部分特性,但也具有独特的、与 B 树不同的特性,不同的地方有以下两点:

    • B+ 树的非叶子结点不直接存储数据的指针,所有数据的指针都存储在叶子结点
    • B+ 树叶子结点存储的数据从小到大有序排列,且相邻叶子结点之间具有链接

    与 B 树的区别

    与 B 树相比较,B+ 树具有以下特点:

    • B+ 树的非叶子结点不直接存储数据,存储的索引更多,树的层级更少,查询的速度更快
    • B+ 树所有数据的指针都存储在叶子结点,因此每次查找到数据的次数都相同,查询速度更稳定
    • B+ 树所有的叶子结点之间具有链接,构成了一个有序链表,查询范围区间的数据更方便
    • B+ 树遍历所有数据时只需要遍历所有叶子结点即可,相对 B 树遍历更快

    为什么使用 B+ 树作为索引结构?

    索引的本质是一种用于快速查找记录的数据结构,常见有二叉查找树、平衡二叉树、哈希表、B 树和 B+ 树等索引存储结构。

    每一种索引结构都有其对应的应用场景,易用性也是选择的标准之一,这里讨论一下为什么选用 B+ 树作为索引存储结构。

    为什么不采用二叉查找树?

    二叉查找树索引

    使用普通的二叉树查找作为索引结构具有一个致命的问题:当一直插入数据的时候,有可能会退化成链表结构,时间复杂度也会从 O(logn) 退化到 O(n)

    因此,普通的二叉查找树比较适合数据基本没有变动的情况,这样查找效率不会发生较大的变化。

    为什么不采用平衡二叉树?

    平衡二叉树索引

    为了解决普通二叉查找树有可能退化成链表的问题,可以使用自平衡的二叉查找树代替,如 AVL 树、红黑树等。

    红黑树常见的一种自平衡二叉查找树,但是也有一个问题:红黑树是一个近似平衡的二叉树,当数据量较大的时候,会出现树层级较大的情况。

    当数据量非常大时,索引占用的空间也会非常大,索引还是得存储在磁盘上,如果树的层级较大,则进行磁盘 IO 的次数就会越多,性能就会越差。

    因此,红黑树不适合作为存储在磁盘上的索引结构。

    为什么不采用哈希表?

    哈希表是一个支持快速查找的数据结构,其查找的时间复杂度是 O(1),其也是最常见的索引存储结构之一。

    但是哈希表也有其缺点,就是只存储键值对应关系的哈希表不支持范围查询,如果要做范围查询,需要做全量的数据扫描才行。

    当然,如果是具有排序功能的哈希表,会非常适合作为存储在内存中的索引结果,如 Java 中的 TreeMap 对象。

    为什么不采用 B 树?

    使用 B 树可以解决红黑树层级较大的问题,通过一个结点可以存储多个元素,树变得更加矮胖,使得树的层级变得可控。

    而且,通过给一个结点存储一页的数据量,最大化地优化操作系统和磁盘的交互,解决了多次磁盘 IO 的问题。

    但是对应 B+ 树而言,B 树的层级仍然会比 B+ 树的高,且范围查询没有 B+ 树方便,这是舍弃 B 树而选择 B+ 树的主要原因。

    当然,也有使用 B 树作为索引结构的数据库,如 MongoDB 等。

  • 相关阅读:
    Elastic Search(一)
    【Vue】Vue开发实战之我的笔记(ch18-ch27)--20221115
    【计算机视觉】OpenCV3编程入门-笔记(一)
    P5194 [USACO05DEC]Scales S
    千挂科技与东风柳汽达成前装量产合作,2024年交付自动驾驶牵引车
    我的python-web基础(Flask前后端不分类)
    Flink开发语言使用Java还是Scala合适?
    DSP CCS12.00 芯片:TMS320F28335 映射的区域的流水灯LED 加上蜂鸣器的使用
    二分图及其多个扩展用法详解及其证明 + 模板题: 关押罪犯 棋盘覆盖
    《嵌入式 - 嵌入式大杂烩》CoreMark性能测试
  • 原文地址:https://www.cnblogs.com/fatedeity/p/16367467.html