4 MySQL学习---MySQL索引( 三 ) _生活百科

B树（平衡二叉树的改造）的引入对于平衡二叉树，考虑到磁盘IO对查询数据效率的影响，我们更希望出现“矮胖”而不是“瘦高”树，因为这样可以显著减少查询时的IO次数，增加查询效率。那么我们如何能够降低树的高度呢？
假如key为8字节（bigint类型），每个节点有两个指针，每个指针为4个字节（B），一个节点占用的空间16个字节（8+4*2=16）
因为在MySQL的InnoDB存储引擎一次IO会读取的一页（默认一页16KB）的数据量，而二叉树一次IO有效数据量只有16字节，空间利用率极低。为了最大化利用一次IO空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16kB/16B=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建100万条数据，树的高度只需要2层就可以（1000*1000=106），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。、
B树又叫多路平衡树，通常我们所说的m阶/m叉的B树，它必须满足以下条件：

树中每个节点最多包含m个子节点
除根节点和叶子节点之外，每个节点至少有[ceil(m/2)]个子节点
若根节点不是叶子节点，则至少有2个子节点
所有的叶子结点都在同一层
每个非叶子节点由n个键和n+1个指针组成，其中[ceil(m/2)-1]<=n<=m-1

B树的主要特点如下：

B树的节点中存储着多个元素，每个内节点有多个分叉。
节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，所有的节点中都储存数据。
父节点当中的元素不会出现在子节点中。
所有的叶子结点都位于同一层，叶节点具有相同的深度，且彼此之间没有指针连接。

B树的简图如下图所示：

文章插图
注：这里限于篇幅，不再详解B树的插入和删除操作，感兴趣可到MySQL学习(5)---B树和B+树详解查看。
应该说，B树已经接近数据库对底层数据结构的要求了，但仍有可以优化的地方。如：

B树不支持范围查询的快速查找，因为它采取了中序遍历的方式。以上图为例，我们要查询2~9之间的数据，在查找到2之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
如果data域中存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

B+树的引入B+树，作为B树的升级版，在B树基础上，MySQL在B树的基础上继续改造，使用B+树结构构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题。