姓B的树主要有三种：B-树（也就是B树），B+树以及B*树。
B-树（B树）
B 树又叫平衡多路查找树。一棵M阶的B树定义如下：
- M阶树，指的是每一个节点最多有M个子节点
- 除了根节点可以有2<= K <=M个子节点之外，其他中间节点的子节点数目必须在M/2(取上限)<= K <=M之间
- 所有叶子节点都出现在同一层，实际上所有的叶子节点都是空指针
- 每一个节点中关键字的个数不其所拥有的子节点少一个，且升序排序
- 2和4的限制导致了对于每一个中间节点，其所有的关键节点的数量为M/2(取上限)-1 <= K <= M-1
B树中的每个结点根据实际情况可以包含大量的关键字信息和分支(当然是不能超过磁盘块的大小，根据磁盘驱动(disk drives)的不同，一般块的大小在1k~4k左右)；这样树的深度降低了，这就意味着查找一个元素只要很少结点从外存磁盘中读入内存，很快访问到要查找的数据.
B树的高度
如果一颗B树所包含的关键字为N，那么怎样求该树的高度呢？
这里先设每一个节点的最小子节点的数量M/2(取上限)为t，那么在第一层，也就是根节点，节点数量为1，第二层的节点数量至少为2，接下来每一层，由于每一个节点的子节点数量为t，于是第三层的节点数为2*t，第四层为2·t·t，一直下去。所以第L层的节点数为2·t^(L-2); 对于B树来说，叶节点的数量为B树的所有关键字N+1，所以对于有N个关键字的B树来说，其叶子节点的层数如果为h的话，那么有2·t^(h-2) = N+1; 这样的话，h = log_t((N+1)/2)+2;由于B树的叶子节点只是一个空指针，在B树中没有表示出来，所以B树的层数为H = log_t((N+1)/2)+1，如果高度从根节点为0算起的话，就是log_t((N+1)/2)，因为上面所有的推导都是在节点的子节点最小的情况下得到的，所以实际上B树的高度要比得到的log_t((N+1)/2)小。
B树的插入删除操作
对于会修改B树结构的操作：插入、删除，在处理的过程中必须保证B树的特征，所以对于插入和删除，需要一些比较复制的处理流程：
插入
插入一个值时，如果对应的节点的关键字恰好为M-1个，那么需要将该节点的关键字的中位数上移到其父节点中，然后该节点剩下的关键字平均分裂为两个新的节点，上移的中位数对于父节点来说其实也是一个插入操作，所以对父节点进行同样的插入造作，这样递归知道没有冲突为止。如果插入的节点的关键字小于M-1，那么直接在该节点中按照关键字的值顺序插入新的关键字。
下面是插入的演示：
1、B树的初始结构：
2、插入H时，结点发现空间不够，以致将其分裂成2个结点，移动中间元素G上移到新的根结点中，在实现过程中，把A和C留在当前结点中，而H和N放置新的其右邻居结点中。如下图：
3、当插入E,K,Q时，不需要任何分裂操作：
4、插入M需要一次分裂，注意M恰好是中间关键字元素，以致向上移到父节点中
5、当B树的结构如下所示时：
6、当插入S时，含有N,P,Q,R的结点需要分裂，把中间元素Q上移到父节点中，但是情况来了，父节点中空间已经满了，所以也要进行分裂，将父节点中的中间元素M上移到新形成的根结点中，注意以前在父节点中的第三个指针在修改后包括D和G节点中。
B树的删除
首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，接下来判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中，然后是移动之后的情况；如果没有，直接进入移动之后的情况。
移动之后的情况：
- 如果当前所在的节点没有子节点，那么在删除后，需要看当前的节点的关键字是个数是否为：
M/2(取上限)-1 <= K <= M-1,如果是的话，删除完成，否则的话，进入向相邻兄弟节点求借关键字步骤。 - 如果的当前的所在节点具有子节点，那么删除后，向该关键字所对应的左或右子节点接一个关键字上移到当前节点中，先借丰满的子节点，移动后不需要修改其他，删除直接完成。如果左右子节点都不是丰满的，那么在上移一个关键字后，需要对被借关键子的子节点进入向相邻兄弟节点求借关键字步骤。
进入向相邻兄弟节点求借关键字步骤
向相邻兄弟节点求借关键字步骤是因为当前的节点的关键子个数不符合M/2(取上限)-1 <= K <= M-1，此时可以看看与当前节点相邻的左右兄弟节点有没有丰满的，有的话，当前节点所对应的父节点的关键子下移到当前节点中，然后丰满兄弟节点的相应的关键子上移到父节点中，放在那个刚下移的关键子的位置上，结束！，如果左右兄弟节点都没有丰满的话，就只能进行节点合并了。节点合并先找出需要合并的左右兄弟节点，二选一，然后将父节点所对应的关键子下移与需要合并的两个节点组成新的节点，此时，父节点相当于删除了一个关键字，那么就需要对父节点进行进入向相邻兄弟节点求借关键字步骤了，一直递归知道B树结构平衡为止！
删除演示：
1、B树的初始结构：
2、首先删除元素H，当然首先查找H，H在一个叶子结点中，且该叶子结点元素数目3大于最小元素数目ceil(m/2)-1=2，则操作很简单，只需要移动K至原来H的位置，移动L至K的位置（也就是结点中删除元素后面的元素向前移动）
3、下一步，删除T,因为T没有在叶子结点中，而是在中间结点中找到，发现他的继承者W(字母升序的下个元素)，将W上移到T的位置，然后将原包含W的孩子结点中的W进行删除，这里恰好删除W后，该孩子结点中元素个数大于2，无需进行合并操作。
4、下一步删除R，R在叶子结点中,但是该结点中元素数目为2，删除导致只有1个元素，已经小于最小元素数目ceil(5/2)-1=2，此时进入进入向相邻兄弟节点求借关键字步骤
5、最后一步删除E，因为没有左右相邻兄弟节点是丰满的，所以进入节点合并步骤：
但是，由于此时的父节点不符合要求，所以需要对父节点在进入进入向相邻兄弟节点求借关键字步骤，很明显，父节点G没有对应可借的兄弟节点，所以进行节点合并
B+树
谈完了B树，我们再来讨论一下B+tree，B+tree是B树的一个变种，在实际应用中，B+tree更加常见。B+树与B树的区别在于这么几点：
1、B+树的内部节点（也就是非叶子节点）有n个关键字，同时有n个儿子。这和B树不同，B树的内部节点有n个儿子，但只有n-1个关键字。
2、B+树只有叶子节点才包含行数据，而内部节点仅仅只有关键字信息和儿子的指针（这里的指针实际上就是磁盘块的文件偏移量），也就是说内部节点仅仅包含索引信息。
3、B+树中的数据都存在于叶子节点中，因此所有叶子节点加在一起所组成的集合包含了所有关键字的信息以及关键字对应的行数据，而B树所有叶子节点加在一起所组成的集合并未包含所有的关键字，因为有些关键字处在内部节点中。
上图就是B+树的一个实例。可以看到叶子节点中，蓝色部分包含了所有关键字信息，一个也不少。图中叶子节点把关键字信息（蓝色）和实际数据（Q）分开了，实际上为了便于理解，你可以认为叶子节点就是一行一行顺序排列的行数据，行数据本身就包含了关键字信息。需要注意的是，中间节点的每一个关键字的值都是其对应的子节点的关键字中的那个最小的值。每一个节点之所以有一个指向其相邻兄弟的指针，是因为可以方便顺序访问，提高区间访问的性能。相比于B树，B+树更适合外存索引，原因和内节点的出度有关，因为B+树的内节点只存储索引信息和子节点的指针信息，少去了B树对应的data信息，所以一个节点所存储的索引信息比B树大很多，这样的话，节点的出度就越高。因为一般在实现B+树的时候，会是将一个节点设置成为一个页的大小，每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O，所以一个节点的出度就取决于存储的key+data+pointer的大小，B+少了data，所以存的索引信息也就越多。
B*树
B-tree是B+-tree的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，B树中非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)·M，即块的最低使用率为2/3（代替B+树的1/2）。给出了一个简单实例，如下图所示：
B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；