B树与B+树 - YHT's Note Repo

%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 总结 B 树与 B+树是 "**自平衡==多叉==搜索树**"，可**保持数据==有序==**，支持在 $O(\log n)$ 时间进行**查询**、**顺序访问**、**插入**和**删除**操作。 > [!info] $M$ 阶 B 树/B+ 树：即**树中每个节点==最多==具有 $M$ 个子节点** ## "B 树" 与 "B+树"的区别 - B 树： - **内部节点**同时存储 **关键字 & 对应数据**。 - B+树： - **内部节点**仅存储 "**关键字**"（索引），**数据**只在 "**==叶节点==**" 存储。 - **叶节点层**构成 "**双向链表**"，支持 "**==范围查询==**"。 > [!NOTE] B+ 树的优点 > > - **索引节点** 仅存储索引而无数据，占用空间小，故**相较于 B 树==单节点可存储更多索引==**，**树的高度将更矮**。 > - **数据全部集中在叶节点**，且叶节点层构成 "**双向链表**" 的形式，故支持**高效的 "==范围查询=="**。 > - 例如，对于 `SELECT * from tbl where t > 10;` 这类查询，在定位到数据 `t=10`后，**即可沿着 next 指针一路查找**。 > - B 树不支持直接的范围查询，范围查询**需要遍历树**。 > > [!info] B+树是关系型数据库的 "**标准索引结构**" > > - MySQL InnoDB 使用 B+树索引（聚簇索引和二级索引） ## B 树/B+树的节点信息 B 树、B+树中节点包含的信息： | | B 树节点 | B +树内部节点 | B+树叶节点 | | ------------ | ----- | --------- | ------ | | **关键字** 数组 | ✔️ | ✔️ | ✔️ | | **数据指针** 数组 | ✔️ | ❌ | ✔️ | | **子节点指针** 数组 | ✔️ | ✔️ | ❌ | | **双向链表**指针 | ❌ | ✔️（部分实现有） | ✔️ | - **关键字** 数组：每个节点内包含 **多个关键字**，**每个关键字** 即为一项数据的 "**==索引==**"，对应一个 "**数据指针**"。 - **数据指针** 数组：指向一项数据的实际位置。 - **子节点指针** 数组：指向子节点的指针。 - **双向链表指针**：B+树的**所有叶子节点**通过 `prev`、`next` 两个指针形成 "**==有序==的双向链表**"，实现 "**范围查询**"。 > [!important] "**关键字**" 即为一项数据的「**==索引==**」，要求 **==唯一无重复==**，与 "**数据指针**" 逐一对应 # B 树 > B-Tree $M$ 阶 B 树定义为： - **根节点**若非叶节点，则 **==至少==有 2 个子节点**。 - 除根节点外，每个**内部节点** 的 **==子节点数量==** 范围为：$\left[{\Large\left\lceil\frac{M}{2}\right\rceil}, M\right]$ - 除根节点外，每个节点的 "**==关键字数量==**" 范围为：$\left[{\Large\left\lceil\frac{M}{2}\right\rceil}-1, M-1\right]$ - 具有 **$k$ 个子节点**的节点，**具有 $k -1$ 个关键字**。 - **关键字==升序==排列**。 - **子节点排列满足 "==搜索树==" 的性质**。 - **所有叶节点均在同一层**。 > [!info] 阶数 $M$ 即每个节点 "**==最多==拥有的子节点数量**" > > 当 $M=100$ 时，**百万**数据量 B+树是 3 层，**亿级**数据量的 B+树是 5 层。 > [!NOTE] B 中每个节点内的 **关键字升序排列**，且其**子节点排列**满足 "**==搜索树==**" 性质 > > ![[Excalidraw-Solution/B树与B+树.excalidraw.md#^group=K69UYEdbhuIRZOYtHxxtC|725]] > > > [!example] 5 阶 B 树 > > ![[_attachment/00-数据结构与算法笔记/数据结构/B树与B+树.assets/IMG-B树与B+树-6F9EF4A89C84984EEFAFF56ABAD89622.png|621]] > > [!example] 3 阶 B 树 > > ![[_attachment/00-数据结构与算法笔记/数据结构/B树与B+树.assets/IMG-B树与B+树-B2DD0BF6E6F31678E8F07098B671D8E2.png|814]] > > # B+ 树 B+ 树是 B 树的变体和升级，更适合实现实际应用中操作系统的**文件索引**和**数据库索引**。 **$M$ 阶 B+树** 进一步具备以下特性： - **内部节点**只存储 "==**关键字**=="，无对应数据，每项关键字为其**相邻后一子树** 中的 **==最小==叶节点关键字**。 - **叶节点** 存储 **关键字&数据**，**所有数据**都只存储在叶节点。 - 部分实现中，**叶节点**不同于内部节点，若其**最多可存储 $N$ 项关键字**，则**至少需存储 ${\Large\left\lceil\frac{N}{2}\right\rceil}$ 项**。 - **叶节点**额外具有 `prev`、`next` 指针，构成一条 "**==有序双向链表==**"，支持 **==范围查询==**（直接遍历叶节点） - 部分实现中，**每层内部节点**也均构成 "有序双向链表"。 > [!example] 5 阶 B+ 树 > ![[_attachment/00-数据结构与算法笔记/数据结构/B树与B+树.assets/IMG-B树与B+树-4009124E16E924C9ED009BDB30E09DD1.png]] > [!example] 4 阶 B+树 > > 部分实现中，**叶节点**不同于内部节点，若其**最多可存储 $N$ 项关键字**（$N\neq M-1$），则**至少需存储 ${\Large\left\lceil\frac{N}{2}\right\rceil}$ 项**。 > > ![[_attachment/00-数据结构与算法笔记/数据结构/B树与B+树.assets/IMG-B树与B+树-3DCE2ACC74C58D1C8A5F7EF7DDDAA6B9.png|629]] > > > > [!quote] > > - Each node, except for the root and the leaves, has $\left[{\Large\left\lceil\frac{M}{2}\right\rceil}, M\right]$ children，and has $\left[{\Large\left\lceil\frac{M}{2}\right\rceil}-1, M-1\right]$ keys. > > - If each leaf can store $N$ records at most（$N$ may be not equal to $M-1$），it must store ${\Large\left\lceil\frac{N}{2}\right\rceil}$ records at least. > # 参考资料 - [B 树 - OI Wiki](https://oi-wiki.org/ds/b-tree/) - [B+ 树 - OI Wiki](https://oi-wiki.org/ds/bplus-tree/) - [B树(B-树)、B+树、R树简介 - mylomen](https://mylomen.com/archives/177) - [notes/docs/B树和B+树详解.md at master · wardseptember/notes · GitHub](https://github.com/wardseptember/notes/blob/master/docs/B%E6%A0%91%E5%92%8CB+%E6%A0%91%E8%AF%A6%E8%A7%A3.md) # Footnotes