如果该元素存在于非叶子节点，那么删除它将会留下一个空位，这时候我们需要一些处理来填充该位置。
因为节点的元素个数在 [M/2, M] 的范围内，所以比如这里我们以 5 阶B-树为例，判断节点元素是否充足即满足个数则至少拥有三（2 + 1）个元素的节点才算是有充足的元素。
如果被删元素的左子树拥有足够的元素，这时候我们只需拿左子节点的最大值元素上来填充即可
当左子树不够元素而右子树元素充足时，这时候我们拿右子树的最小值元素上来进行填充
当左右子树所含元素均不足时，但左子树的左边兄弟节点的元素个数充足，这时我们需要拿左边的兄弟节点来进行调整。
当左右子树所含元素均不足时，但左子树的左边兄弟节点的元素个数也不足时，这时候我们还是拿左子树的最大值元素进行填充，之后再将该节点与其他节点合并形成新的节点。
B+TreeB-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。
与B-Tree相比，B+Tree有以下不同点：
每个节点的指针上限为2d而不是2d+1。
B+Tree叶子节点保存了父节点的所有关键字和关键字记录的指针，每个叶子节点的关键字从小到大链接
内节点不存储data，只存储key；叶子节点不存储指针。因此所有数据地址必须要到叶子节点才能获取到，所以每次数据查询的次数都一样。
红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
下面先介绍内存和磁盘存取原理，然后再结合这些原理分析B-/+Tree作为索引的效率。
磁盘存取原理索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。
下面是磁盘的整体结构示意图：
一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。
下面是磁盘结构的示意图：
盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。
当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。
局部性原理与磁盘预读由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。
这样做的理论依据是计算机科学中著名的局部性原理：
当一个数据被用到时，其附近的数据也通常会马上被使用。
程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。