B-树、B+树和B*树

用途：Mysql数据库里面的索引主要基于Hash和B+树。

B-树

（读作B shu，中间不是减号）一句话总结：就是矮胖版的搜索二叉树。
为什么要矮胖？主要是减少磁盘的IO。因为对海量数据，索引也是非常大的，可能有几个G。所以树可能要存在不同的磁盘页中，每次磁盘页只能逐一加载到内存中。树的查找是从根要叶子，最坏情况下，每到一个节点都要加载一次磁盘页，所以，矮胖的话，就是少走一些节点。图解：

要变“矮胖”，就是由二叉变成“多叉”，每个节点也可以存多个元素。具体规则如下（也没看太懂）：
1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

看例子说话，其实比较像二叉搜索树（BST）：

性能说明：
1.查询：其实比较次数不比二叉树少，但是这个消耗是在内存中；
2.插入：比较复杂，也是从根开始找插在哪里，但是有时候涉及到节点的分裂。因为涉及到节点存的元素超过了规定。例如插入4,那么35这个肯定是要分裂的；
3.删除：比较复杂，涉及到节点的旋转。比如，删除11的话，要把12补位到11的位置上，再把13作为根。

应用：
文件系统，非关系型数据库，例如MongoDB

B+数

一句话总结：是有序的链表，同时向上建立了B-树的索引。

看例子说话：

简单的理解，就是最下面是有序链表，然后上面每层都是把自己的子节点的最大值存起来，例如根节点中，8就是左子树最大，15就是所有数据的最大。叶子节点包含了B+树的所有信息。

具体规则如下（其实不是很懂）：
1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

另外一个特点（不是很理解）：B-树是每个节点都有卫星数据（索引？），但是B+树只有叶子节点存有卫星数据。

性能说明：
1.查询：
和B-树差不多，但是B+树的父节点都没有存卫星数据，所以一个磁盘页可以存更多的节点。B+树也更“矮胖”；
B+树每次都必须查到叶子节点，B-树可能在前面就终止了，所以B+树更为稳定；
B+树的范围查询更为简单，查到头元素之后，直接链表向后找，就能确定范围。

B*树

一句话总结：在B+树的基础上，其他节点再增加指向兄弟节点的指针。

B*树相对B+树的提升主要在插入数据上，在需要节点分裂的时候，一个节点满了的时候，可以将一部分多的数据移到兄弟节点中，这样就减少了新增节点的概率。