本文可以理解为是这个视频的笔记，感兴趣的同学强烈推荐观看原视频，作者阐述深入浅出，十分完善。
Abdul在这个视频开始就说了一句非常精彩的话
在内存里管理数据用的是数据结构，而在硬盘里管理数据用的都属于数据库管理系统（DBMS）
所以B树/B+树和一般的数据结构相比，例如红黑树或者二叉树等，给人的感觉上很不一样。这种不一样最明显的体现就是，B树的来源，即B树是在怎么样的背景下被引导出来的？为什么B树有着这样的性质和这样的插入方式？这些问题都会在本文中得到解答。
1. 机械硬盘的基本性质
- 机械硬盘（spinning disk），可以简单地理解为一个圆盘被划分成了很多同心圆环，同时又被划分为很多扇形区域。圆环称为轨道（track），而扇形区域称为片区（sector）
- 每一个轨道和片区的交集称为一个块（block）
- 每一个块有着相同的大小，例如 512B
- 所以根据以上的性质，想要访问硬盘上的某一个字节（Byte），需要轨道编号、片区编号、以及block内的偏移量（offset），这样就可以完全对应上一个字节。
2. 数据索引
假设我们现在有一组数据，里面有一百条记录（可以理解为键值对），每一条记录占用的空间是128字节。那么很容易就可以得到，一个512字节大小的block能够存储4条记录，为了存储100条记录，最少需要25个block。此时如果我们需要按键查找某条记录，那么我们最多需要访问25个block，才能找到相对应的记录。本文的剩余内容就是围绕如何降低最多需要遍历的block数量展开的。
由此便有了数据索引的概念，即将每一条记录的键和该条记录对应的硬盘地址单独拿出来组成一条新的记录。假设我们需要10个字节来存储一个键，6个字节来存储一个硬盘地址。因此，需要16个字节来存储一条数据索引，总共需要1600字节来存储整个100条记录的索引。意味着这个索引需要至少4个block来存储。到这里，我们的按键查找操作所需要访问的最大block数目已经从原先的25个降低到了5个（4个索引block，1个存记录的block）。
3. 多层数据索引
可以看到数据索引对按键查找的优化是很显著的，那么还可以更进一步吗？由此便引出了多层索引，即索引的索引。之前的索引可以认为只是将键和地址取出，以压缩其他的信息。那么多层索引则是运用了类似二叉查找的思想，将所有一级索引（将之前的索引简称为一级索引）按键排序并分块。不妨假设每一块包含32个一级索引，那么之前的100个一级索引需要至少4个二级索引。4个索引只需占用一个block，至此按键查找所需访问的最大block数目从5个又降低到了3个（一个二级索引，一个一级索引，一个数据记录）。整个结构大致如下图所示。
4. 多路查找树
如果把上图的结构旋转一下，就可以得到类似B树的结构。在正式引出B树之前，还需要有一个概念，那就是多路查找树，或者称为m路查找树，一般的二叉搜索树即是二路查找树。m称为多路查找树的阶数。该树有如下性质
- m路查找树的任意一个非叶子结点至多拥有
m个孩子节点。 - 每一个节点至多有
m-1个键
5. B树 = 多路查找树 + 额外性质
这些额外性质包括
- 任意一个非叶子结点至少包含
Math.ceil(m / 2)个孩子节点， 根节点例外（根结点至少有两个孩子节点） - 所有叶子结点均在同一层，即所处树的深度一致
- 插入操作是自底向上进行的
其中最后一点是B树的精华所在，即索引的结构及数量是根据实际数据量自动调整的，这也符合我们前面所提到的索引构建过程，即数据–>一级索引–>二级索引–>……
具体的插入过程网上已经有大量的文章了，这里就不赘述了。同时，删除操作其实和插入操作的逆向很相似。并且正如Abdul说的那样，大家不用太在意在插入删除过程中的一些细节问题，例如结点分裂的时候到底是位于Math.ceil(m / 2)的键上移还是位于Math.ceil(m / 2) + 1的键上移，结点合并的时候到底是和左兄弟结点合并还是右兄弟。这些细节问题完全取决于具体实现者的偏好，只需记住以上的性质不被破坏即可。
6. B+树 = B树 + 额外性质
这里的额外性质主要就是一条
- 所有的非叶子结点均不存储实际的索引，只存键
这样做的目的或者说好处即在非叶子结点可以存储的键更多了，因为非叶子结点不再需要存储实际的指向硬盘数据的指针，因此可以存储更多的键以及更多的指向孩子节点的指针（即分叉更多）。所以同样结构的B+树能够存储更多的索引。
