在YouTube上有个视频将B树深入浅出讲的十分透彻，简单整理笔记如下。
disk structure
机械磁盘的物理架构，是由多个盘面、中心柱和机械臂组成的。中心柱串起多个盘面，每个盘面上都有机械臂靠伸入、伸出以及旋转盘面实现对整个盘面的访问。盘面的track，指的是一条圆形轨道，盘面有大大小小的多个track。盘面的sector，指的是一个最小单位的扇形面积，所有sector构成了盘面这个圆。track no和sector no唯一标识一个block，它是磁盘分配的最小单位。假设我们要写10条记录到硬盘，他们背后就是写在一系列block。
indexing
假设我们在磁盘存储了100个记录，每次要找指定id的记录我们都得从头扫描，代价非常昂贵。其实可以把间隔10个记录存索引，如把指向1、10、20等的地址信息存到索引文件，每次查询指定id记录时先加载索引文件，然后根据地址信息再去扫描实际数据记录。这就是indexing的思想。
multi-indexing和m-way search tree
假设磁盘的记录是1W、10W和100W个呢？这时上述的索引文件将非常庞大，必须在索引文件之上再建索引，再建一层索引可能还是太大难以一次load到内存，重复这个动作直至最上面一层的索引文件足够小。这就叫multi-indexing，即多层索引。
把上面的多层索引竖着拎起来，它就是一颗m-way search tree。查找记录时一层层索引往下找，直到到达最底下一层的实际记录层。索引的组织之所以不用binary-search tree，是因为同等节点存储在binary-search tree的深度更深，而每向下一层都涉及到磁盘读I/O，读I/O次数较m-tree要多的多。m-way search tree虽然一次读了较多数据到内存，到它减少了较重的I/O操作，也是一种空间（主存）换时间的思想。
b-tree
上面的记录在实际工程中，是存储在数据库的。b-tree其实就是数据库规定的一种m-way search tree语法，通过规定该语法实现了索引结构的增、删、改自维护，它的目的是使得m-way search tree能自适应。
b-tree有以下规定：
- 每个节点最多有m个孩子，根节点（非叶子）至少有2个孩子，其他非叶子节点至少有Ceil(m/2)个孩子
- 所有叶子节点都在同一层
- 每个节点包含n个关键字信息（真实记录数据），关键字的个数n满足ceil(m/2)-1 <= n <= m-1，且关键字呈升序排序，即关键字k1 < k2 < … < ki < kn
- 每个非叶子节点有n+1个指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki，但都大于关键字k(i-1)
更多b-tree细节见b-tree。
b+ tree
b-tree的特点是所有数据都存储在节点上。假设我们要发起一个数据库的全表扫描，b-tree的结构将会导致不断上下回溯索引，正因此才有了b+ tree。它和b-tree的不同在于：
- 非叶子节点只存储指针索引信息，不存真实数据
- 真实数据记录都存放在叶子节点中
- 所有叶子节点之间都有一个链指针以便于顺序查找
更多细节参考b+ tree