B树基础
二分搜索树
二分搜索树（BST）是一种有序的内存数据结构，可以用来高效的进行键值查找。二分搜索树由多个节点组成，每个树节点由一个键，一个与该键关联的值以及两个子节点指针组成。二分搜索树从称为根节点的单一节点开始。一颗二分搜索树中只能有一个根节点。
每个节点将搜索空间分为左子树和右子树，一个节点的键大于其左子树中存储的任何键，且小于其右子树中存储的任何键。
从根节点开始一直沿着节点的左指针向下可以到达叶子层的一个节点，此节点持有树中最小键以及与其关联的值。类似的，沿着右指针往下可以找到持有树中最大键预计与其关联的节点。另外，这种结构允许将值存储在树中的所有节点中。对于从根节点开始的搜索，如果在更高层上找到了搜索到的键，则搜索可能在到达树的底部之前终止。
B树的层次结构
B树由多个节点组成。每个节点最多可容纳N个键和N+1个指向子节点的指针。这些节点在逻辑上分为三类：
- 根节点：根节点没有父节点，是树的顶端
- 叶节点：叶节点是没有子节点的底层节点
- 内部节点：连接根节点和叶节点的其他节点，B树通常包含多层的内部节点
由于B树是一种页组织技术，所以节点和页这两个术语在描述中可相互替换。
节点容量与其实际持有的键的个数之间的关系称为占用率。
B树的特征在于其扇出：存储在每个节点中的键的个数。为保持树的平衡需要做出一些结构上的更改，而更高的扇出则有助于均摊这些更改的所带来的开销。同时，通过在单个块或多个连接块中存储指向子节点的键和指针，可以减少寻道的次数。平衡操作会在节点已满或几乎为空时被触发。
B+树：B树允许在根节点、内部节点和叶节点当中任意层上存储值。而B+树则仅在叶节点中存储值，其内部节点仅存储分隔键，用于指引搜索算法去找到叶节点上的关联值。由于B+树中的值仅存储在叶节点这一层上，所以所有操作仅影响叶节点，并且这些操作仅在分裂和合并期间才会传播到更高层。
分隔键
存储在B树节点中的键称为索引条目、分隔键或者分隔符单元格。它将分隔成子树，其持有包含对应键的范围。键存储时已经排好序，以便使用二分搜索。节点中的第一个指针指向小于第一个键的数据所在的子树，节点中的最后一个指针指向大于或等于最后一个键的数据所在的子树。
B树的查找算法
该算法从根节点上开始执行二分搜索算法，将要搜索的键与存储在根节点的键进行比较，直到大于要搜索的键的第一个分隔键。这样便定位了一个要搜索的子树。正如前面讨论的，索引键将树分割成多个子树，子树的边界位于两个相邻的键之间。一旦找到子树，我们就顺着相应的指针继续相同的搜索过程，直到我们到达目标的叶节点。在那里我们要么定位到了搜索的键，要么通过定位它前驱节点而得出它不存在的结论。
在进行单点查询时，在找到或找不到所搜索的键之后搜索便结束了。而在进行范围扫描时，迭代从找到最近的键值开始，并顺着同级指针继续移动，直到到达范围的末尾。
B树的分裂
在B树中，更新操作则通过使用查找算法定位目标叶节点并将新值与现有键相关联来完成。如果目标没有足够的可用空间，我们就说该节点溢出，此时必须将其分裂为两部分才能放入新的数据。更准确的说，如果以下条件成立，则需要分裂节点：
- 对于叶节点：如果节点最多可以容纳N个键值对，且再插入一个键值对将使其超过最大容量N
- 对于非叶节点：如果节点最多可以容纳N+1个指针，且再插入一个指针将使其超过最大容量N+1
分裂是通过分配新节点，将一般元素从原分裂节点传输给它并将添加它的第一个键和指向父节点的指针来完成的。在这种情况下，我们说这个键被提升了。执行分裂处的数组下标称为分裂点。分裂点之后的所有元素都被传输到新创建的兄弟节点，其余元素保留在分裂节点中。
如果父节点已满，即没有容纳被提升的键和指向新创建的节点的指针的空间时，也必须分裂父节点。此操作可能会一直递归传播到根节点。
总之，节点分裂分为四个步骤：
- 分配一个新的节点
- 将一半元素从分裂节点复制到新节点
- 将新元素放入相应节点
- 在分裂节点的父节点处，添加一个分隔键和指向新节点的指针