B-Tree
B-Tree即B树，是一种为磁盘等存储设备而设计的多路平衡查找树，很多数据库系统都使用了B树或者B树的各种变种来存取信息（InnoDB使用了B+树）。
m阶B树的定义
- 树中每个节点最多含有m（m >= 2）个孩子
- 除根节点和叶节点外，每个节点最少有ceil（m/2）个孩子
- 若根节点不是叶节点，那么根节点最少有2个孩子
- 所有叶节点位于同一层，叶节点中不包含任何信息，可以当做外部节点或者查询失败的节点
- 每个非叶节点的节点包含n个关键字信息：n，p0，k1，p1，k2……p（n-1），k（n-1），pn，kn。其中，k（1…n）表示关键字，同一个节点中的关键字按递增次序排列，p(0…n)表示指向子树的指针，pi指向的子树中的所有关键字的值都大于p（i-1）并且小于p（i）。
B+树
B+树是应文件系统所需而产生的一种B-树的变形树。一棵m阶的B+树和m阶的B树的差异在于：
- 有n 棵子树的结点中含有n 个关键码；
- 所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。
- 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大关键码。
通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根节点开始查找。
在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时，若非终端结点上的关键码等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。