1. B树
1.1 定义
B树是多路平衡查找树、自平衡树
即“阶”定义为一个节点的子节点数目的最大值
m阶B-树的定义:其中m>2，m的大小取决于磁盘页的大小
1.非叶子节点的根节点至少有2个孩子
2.每个非根和非叶子节点的节点至少有ceil(m/2)(ceil向上取整)个孩子，至多有M个孩子
3.每个非根和非叶子节点的节点至少有ceil(m/2-1)个关键字，至多有m-1个关键字，且以升序排列,
4.所有叶子节点都在同一层
1.2 B-树的查找
B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键码的有序表，在到达某个结点时，先在有序表中查找，若找到，则查找成功；否
则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键码。
在B-树中进行查找包含两种基本操作:
(1) 在B-树中查找结点；
(2) 在结点中查找关键字。
由于B-树通常存储在磁盘上，则前一查找操作是在磁盘上进行的，而后一查找操作是在内存中进行的，即在磁盘上找到指针p所指结点后，先将结点中的信
息读入内存，然后再利用顺序查找或折半查找查询等于K的关键字。显然，在磁盘上进行一次查找比在内存中进行一次查找的时间消耗多得多。因此，在磁
盘上进行查找的次数、即待查找关键字所在结点在B-树上的层次树，是决定B树查找效率的首要因素
1.3 B树的插入
首先通过查找确定插入的位置。然后在恰当的叶子结点中添加关键码，如果该结点中关键码不超过m-1个，则插入成功。否则要把这个结点分裂为两个把中间的一个关键码拿出来插到结点的父结点里去。父结点也可能是满的，就需要再分裂，再往上插。最坏的情况，这个过程可能一直传到根，如果需要分裂根，由于根是没有父结点的，这时就建立一个新的根结点。插入可能导致B-树朝着根的方向生长。
如下图所示为3阶的B-树(图中略去叶子结点)，假设需依次插入关键字30，26，85。
插入30，如下图所示
插入26，如下图依次所示
插入85，如下图依次所示
1.4 B树的删除
与插入关键字相反，若在B-树上删除一个关键字，则首先应找到该关键字所在结点，并从中删除。
1.4.1 假若所删关键字所在结点并非最下层的非终端结点
假设待删关键字为Ki，此时可以用Ai所指子树中的最小关键字X替代，然后删除关键字X即可。例如，在下图中删除45，可以用f结点中的50代替45，然后在f结点中删除50。
删除50后的B-树如下图所示
1.4.2 若该结点为最下层的非终端结点，且其中的关键字数目不少于ceil(m/2)，则删除完成，否则要进行“合并”结点的操作
合并可以分为下面三种情况去处理（算出结点关键字的取值范围，只要是不在范围内就进行合并操作，3阶B-树关键字的范围为[1,2]）
(1) 被删关键字所在结点中的关键字数目不小于ceil(m/2)，则只需从该结点中删去该关键字Ki和相应指针Ai，树的其它部分不变，例如，从1.4.1图(a)所示
B-树中删去关键字12，删除后的B-树如下图所示：
(2) 被删关键字所在结点中的关键字数目等于ceil(m/2)-1，而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于ceil(m/2)-1，则需将其兄弟结点中
的最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。例如，从1.4.1图(a)
中删去50，需将其右兄弟结点中的61上移至e结点中，而将e结点中的53移至f，从而使f和g中关键字数目均不小于ceil(m-1)-1，而双亲结点中的关键字数目不变，结果如下图所示。
思考：就(2)结果图的B-树中删去关键字24之后，B-树的形状，文章最后给出。
(3) 被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于ceil(m/2)-1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，
则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到 Ai所指兄弟结点中(若没有右兄弟，则合并至左兄弟结点
中)。例如，从(2)结果图所示 B-树中删去53，则应删去f结点，并将f中的剩余信息(指针“空”)和双亲e结点中的61一起合并到右兄弟结点g中。删除后的树如下图所示。
如果因此使双亲结点中的关键字数目小于ceil(m/2)-1，则依次类推。例如，在(3)结果图的B-树中删去关键字37之后，双亲b结点中剩余信息(“指针c”)应
和其双亲a结点中关键字45一起合并至右兄弟结点e中，删除后的B-树如图下所示。
总结：
删除元素，移动相应元素之后，如果某结点中元素数目(即关键字数)小于ceil(m/2)-1，则需要看其某相邻兄弟结点是否丰满(结点中元素个数大于
ceil(m/2)-1)如果丰满，则向父节点借一个元素来满足条件；如果其相邻兄弟都刚脱贫，即借了之后其结点数目小于ceil(m/2)-1，则该结点与其相邻的某一兄弟结点进行“合并”成一个结点，以此来满足条件。
2. B+树
2.1 定义
B+树是基于B-树的，增加了如下规则：
(1) 有k个子树的非终端结点包含有k个关键码（B树中是k-1个关键码），每个关键码不保存数据，只用来索引，所有数据都保存在叶子节点。
(2) 所有的叶子结点中包含了全部关键码的信息，及指向含这些关键码记录的指针，且叶子结点本身按照关键字的大小自小而大顺序链接。
(3) 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。
如图一棵3阶的B+树:
通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根节点开始，进行随机查找。
在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时，若非终端结点上的关键码等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。
相关面试题
题目1： Mysql数据库用过吧？里面的索引是基于什么数据结构。
答：主要是基于Hash表和B+树
题目2： 很好请你说一下B+树的实现细节是什么样的？B-树和B+树有什么区别？联合索引在B+树中如何存储？
答: 首先，数据库使用树型结构来增加查询效率，并保持有序。那么，为什么不使用二叉树来实现数据结构呢，二叉树算法时间复杂度是lg(N)，查询速度和比较次数都是较小的。
实际上，查询索引操作最耗资源的不在内存中，而是磁盘IO。索引是存在磁盘上的，当数据量比较大的时候，索引的大小可能达到几个G。那么，我们利用索引进行查询的时候，不可能把索引直接加载到内存中，只能一次读取一个磁盘页，一个磁盘页对应着一个节点，一次读取操作时一个磁盘IO。在二叉树查询时，最坏的情况下查找的次数是树的高度，即IO次数为树的高度。B-树就是比二叉树“矮胖”的树。
B-树查询的次数并不比二叉树的次数小，但是相比起磁盘IO速度，内存中的比较产生的耗时就不足为提了。所以只要树的高度足够低，IO次数少，就可以提升查找性能。而每个节点中有多个元素，都只在内存中操作。所以，B+树对比B-树有如下好处：
IO次数少：B+树中间节点只存索引，不存在实际的数据，所以可以存储更多的数据。索引树更加的矮胖，IO次数更少。
性能稳定：B+树数据只存在于叶子节点，查询性能稳定
范围查询简单：B+树不需要中序遍历，遍历链表即可。
MyISAM索引
主键索引
MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。
辅助索引
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。
MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做“非聚集索引”。
InnoDB索引
主键索引
MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。InnoDB的索引方式也叫做“聚集索引”。
辅助索引
InnoDB的所有辅助索引都引用主键作为data域。
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。 不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
InnoDB索引和MyISAM索引的区别：
一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。
思考答案：
