前言

首先，B树不要和二叉树混淆，在计算机科学中，B树是一种自平衡树数据结构，它维护有序数据并允许以对数时间进行搜索，顺序访问，插入和删除。

B树是二叉搜索树的一般化，因为节点可以有两个以上的子节点。[1]与其他自平衡二进制搜索树不同，B树非常适合读取和写入相对较大的数据块（如光盘）的存储系统。

它通常用于数据库和文件系统。

先了解磁盘存储

电脑存储用磁盘来存储，存储规则如图，用轨道和block来分区，使得将一块磁盘分成不同的区。

当我们要在磁盘上找到一个数据时，我们需要用地址来查找，而这个地址就是【轨道+block】能够找到指定分区。

找到信息后，我们需要将磁盘上的信息拷贝到RAM上，因为我们不能在磁盘上进行信息处理。

在磁盘上找信息

假设每个块大小512byte。现在要存储数据：一共五个字段，共128byte。（id：10bytes）一共有100条数据。

意味着每个block可以存4条记录。需要25个block来存。

现在想一下，如果需要占用25个block。当我们访问数据，搜索数据的速度取决于你访问的block数量。如果搜索整个表，则需要搜索25个block。

建立索引

数据库的索引就是为了减少访问时间而设计的。

当我们建立索引，我们会在另一个block建立一张表，表里是（我们的【索引值】和指向磁盘的【指针】）。每个数据表的记录都有一个索引条目这就是紧张索引

假设索引值id：10bytes， 指针6bytes。那么一条记录16bytes。

那么一个block能存32个索引条目，那么上面的100条数据就需要4个block来存储索引。

假如数据库的条目指数级倍增，那么我们可以建立索引的索引，又叫做稀疏索引

现在假如我们有很多个稀疏索引，和很多个紧张索引

再将他们旋转90°，就很像一个树状结构了。

这就是B树在数据库中的应用。

B树（B-）树

动机（motivation）

性质

1. 每个节点最多有m个分支（子树）；而最少分支数要看是否为根节点，如果是根节点且不是叶子节点，则至少有2个分支，非根非叶节点至少有【m/2】个分支 。

2. 有n（k≤n≤m）个分支的节点有n-1个关键字，它们按递增排序。k=2（根节点）或【m/2】（非根节点）

3. 节点互不重复。

4. 叶节点处于同一层；可以用空指针表示，是查找失败到达的位置。

基础知识

根节点：根节点就是最上面的节点，B树的根节点可能不是一个，

内部节点：内部节点是除叶子节点和根节点之外的所有节点，拥有父节点和子节点。

叶子节点：叶子节点对元素的数量有相同的限制，但是没有子节点，也没有指向子节点的指针。

阶：就是每一个节点表假如有四个元素，那么它就有五个指针，阶数为5。

插入和删除

建议直接看视频更好理解。
https://www.bilibili.com/video/BV1UC4y1p7zm?from=search&seid=2406874848049670294

https://www.bilibili.com/video/BV1Aa4y1j7a4?from=search&seid=2406874848049670294