（点击
上方蓝字
，快速关注我们)
来源：伯乐在线 - fullstackyang
网址：
http://blog.jobbole.com/105644/
零、铺垫
在介绍B树之前，先来看另一棵神奇的树——二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：
![]()
从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）。
所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）
一、B树的起源
B树，最早是由德国计算机科学家Rudolf Bayer等人于1972年在论文 《Organization and Maintenance of Large Ordered Indexes》提出的，不过我去看了看原文，发现作者也没有解释为什么就叫B-trees了，所以把B树的B，简单地解释为Balanced或者Binary都不是特别严谨，也许作者就是取其名字Bayer的首字母命名的也说不定啊……
二、B树长啥样
还是直接看图比较清楚，图中所示，B树事实上是一种平衡的多叉查找树，也就是说最多可以开m个叉（m>=2），我们称之为m阶b树，为了体现本博客的良心之处，不同于其他地方都能看到2阶B树，这里特意画了一棵5阶B树 。
![]()
总的来说，m阶B树满足以下条件：
-
每个节点至多可以拥有m棵子树
-
根节点，只有至少有2个节点（要么极端情况，就是一棵树就一个根节点，单细胞生物，即是根，也是叶，也是树)。
-
非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整，图中5阶B树，每个节点至少有3个子树，也就是至少有3个叉)
-
非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An]，，其中n表示该节点中保存的关键字个数，K为关键字且Ki
-
从根到叶子的每一条路径都有相同的长度，也就是说，叶子节在相同的层，并且这些节点不带信息，实际上这些节点就表示找不到指定的值，也就是指向这些节点的指针为空
B树的查询过程和二叉排序树比较类似，从根节点依次比较每个结点，因为每个节点中的关键字和左右子树都是有序的，所以只要比较节点中的关键字，或者沿着指针就能很快地找到指定的关键字，如果查找失败，则会返回叶子节点，即空指针。
例如查询图中字母表中的K
-
从根节点P开始，K的位置在P之前，进入左侧指针
-
左子树中，依次比较C、F、J、M，发现K在J和M之间
-
沿着J和M之间的指针，继续访问子树，并依次进行比较，发现第一个关键字K即为指定查找的值
三、Plus版——B+树
作为B树的加强版，B+树与B树的差异在于
-
有n棵子树的节点含有n个关键字（也有认为是n-1个关键字）
-
所有的叶子节点包含了全部的关键字，及指向含这些关键字记录的指针，且叶子节点本身根据关键字自小而大顺序连接
-
非叶子节点可以看成索引部分，节点中仅含有其子树（根节点）中的最大（或最小）关键字
![]()
B+树的查找过程，与B树类似，只不过查找时，如果在非叶子节点上的关键字等于给定值，并不终止，而是继续沿着指针直到叶子节点位置。因此在B+树，不管查找成功与否，每次查找都是走了一条从根到叶子节点的路径
三、MySQL是如何使用B树的
说明：事实上，在MySQL数据库中，诸多存储引擎使用的是B+树，即便其名字看上去是BTREE。
3.1 innodb的索引机制
先以innodb存储引擎为例，说明innodb引擎是如何利用B+树建立索引的
首先创建一张表：zodiac，并插入一些数据
CREATE
TABLE
`zodiac`
(
`id`
int
(11)
NOT NULL
AUTO_INCREMENT
,
`name`
char
(4)
NOT NULL
,
PRIMARY KEY
(`id`),
KEY
`index_name`
(`name`)
);
insert
zodiac(id,name)
values
(1,
'鼠'
);
insert
zodiac(id,name)
values
(2,
'牛'
);
insert
zodiac(id,name)
values
(3,
'虎'
);
insert
zodiac(id,name)
values
(4,
'兔'
);
insert
zodiac(id,name)
values
(5,
'龙'
);
insert
zodiac(id,name)
values
(6,
'蛇'
);
insert
zodiac(id,name)
values
(7,
'马'
);
insert
zodiac(id,name)
values
(8,
'羊'
);
insert
zodiac(id,name)
values
(9,
'猴'
);
insert
zodiac(id,name)
values
(10,
'鸡'
);
insert
zodiac(id,name)
values
(11,
'狗'
);
insert
zodiac(id,name)
values
(12,
'猪'
);
对于innodb来说，只有一个数据文件，这个数据文件本身就是用B+树形式组织，B+树每个节点的关键字就是表的主键，因此innode的数据文件本身就是主索引文件，如下图所示，主索引中的叶子页（leaf page）包含了数据记录，但非叶子节点只包含了主键，术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起，因此这种索引被称为聚簇索引，或聚集索引。
