B+树 | MySQL索引使用原则

MySQL一向相识得都不多，之前写sql筹备提交出产情形之前的时辰，老员工帮我搜查了下sql，让修改了一下存储引擎，其时我行使的是Myisam，后头改成InnoDB了。为什么要改成这样，之前都没有听过存储引擎，于是网上查了一下。

究竟上行使差异的存储引擎也是有很大区此外，下面猿友们可以相识一下。

一、存储引擎的较量

注：上面提到的B树索引并没有指出是B-Tree和B+Tree索引，可是B-树和B+树的界说是有区此外。

在 MySQL 中，首要有四种范例的索引，别离为： B-Tree 索引， Hash 索引， Fulltext 索引和 R-Tree 索引。

B-Tree 索引是 MySQL 数据库中行使最为频仍的索引范例，除了 Archive 存储引擎之外的其他全部的存储引擎都支持 B-Tree 索引。Archive 引擎直到 MySQL 5.1 才支持索引，并且只支持索引单个 AUTO_INCREMENT 列。

不只仅在 MySQL 中是云云，现实上在其他的很大都据库打点体系中B-Tree 索引也同样是作为最首要的索引范例，这首要是由于 B-Tree 索引的存储布局在数据库的数据检索中有很是优秀的示意。

一样平常来说， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的布局来存储的，也就是全部现实必要的数据都存放于 Tree 的 Leaf Node(叶子节点) ，并且到任何一个 Leaf Node 的最短路径的长度都是完全沟通的，以是我们各人都称之为 B-Tree 索引。虽然，也许各类数据库(或 MySQL 的各类存储引擎)在存放本身的 B-Tree 索引的时辰会对存储布局稍作改革。如 Innodb 存储引擎的 B-Tree 索引现实行使的存储布局现实上是 B+Tree，也就是在 B-Tree 数据布局的基本上做了很小的改革，在每一个Leaf Node 上面出了存放索引键的相干信息之外，还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息(增进了次序会见指针)，这首要是为了加速检索多个相邻 Leaf Node 的服从思量。

InnoDB是Mysql的默认存储引擎(Mysql5.5.5之前是MyISAM)

也许对付没有相识过索引的猿友这样看这篇文章异常吃力，这类猿友有须要先对Mysql索引有个概略的相识，可以看看其它一篇文章： 数据库查询优化——Mysql索引http://blog.csdn.net/u013142781/article/details/51424174看完这篇文章我们再转头看看上面的笔墨声名吧。

接下来我们先看看B-树、B+树的观念。弄清晰，为什么加了索引查询速率会加速?

二、B-树、B+树观念

B树

即二叉搜刮树：

1、全部非叶子结点至多拥有两个儿子(Left和Right);

2、全部结点存储一个要害字;

3、非叶子结点的左指针指向小于其要害字的子树，右指针指向大于其要害字的子树;

如：

B-树

是一种多路搜刮树(并不是二叉的)：

1、界说恣意非叶子结点最多只有M个儿子;且M>2;

2、根结点的儿子数为[2, M];

3、除根结点以外的非叶子结点的儿子数为[M/2, M];

4、每个结点存放至少M/2-1(取上整)和至多M-1个要害字;(至少2个要害字)

5、非叶子结点的要害字个数=指向儿子的指针个数-1;

6、非叶子结点的要害字：K[1], K[2], …, K[M-1];且K[i] < K[i+1];

7、非叶子结点的指针：P[1], P[2], …, P[M];个中P[1]指向要害字小于K[1]的子树，P[M]指向要害字大于K[M-1]的子树，其余P[i]指向要害字属于(K[i-1], K[i])的子树;

8、全部叶子结点位于统一层;

如：(M=3)

B-树的搜刮，从根结点开始，对结点内的要害字(有序)序罗列办二分查找，假如掷中则竣事，不然进入查询要害字所属范畴的儿子结点;一再，直到所对应的儿子指针为空，或已经是叶子结点;

B-树的特征：

1、要害字荟萃漫衍在整颗树中;

2、任何一个要害字呈现且只呈此刻一个结点中;

3、搜刮有也许在非叶子结点竣事;

4、其搜刮机能等价于在要害字全集内做一次二分查找;

5、自动条理节制;

因为限定了除根结点以外的非叶子结点，至少含有M/2个儿子，确保告终点的至少操作率。

以是B-树的机能老是等价于二分查找(与M值无关)，也就没有B树均衡的题目;

因为M/2的限定，在插入结点时，假如结点已满，必要将结点破碎为两个各占M/2的结点;删除结点时，需将两个不敷M/2的兄弟结点归并;

B+树

B+树是B-树的变体，也是一种多路搜刮树：

1、其界说根基与B-树同，除了：

2、非叶子结点的子树指针与要害字个数沟通;

3、非叶子结点的子树指针P[i]，指向要害字值属于[K[i], K[i+1])的子树(B-树是开区间);

5、为全部叶子结点增进一个链指针;

6、全部要害字都在叶子结点呈现;

如：(M=3)

B+的搜刮与B-树也基内情同，区别是B+树只有到达叶子结点才掷中(B-树可以在

非叶子结点掷中)，其机能也等价于在要害字全集做一次二分查找;

B+的特征：

1、全部要害字都呈此刻叶子结点的链表中(浓密索引)，且链表中的要害字刚好是有序的;

2、不行能在非叶子结点掷中;

3、非叶子结点相等于是叶子结点的索引(稀少索引)，叶子结点相等于是存储(要害字)数据的数据层;

4、更得当文件索引体系;

相识B-/B+树的观念之后，我们继承说明B+树进步服从的道理。

三、B+树索引道理

如上图，是一颗b+树，关于b+树的界说可以拜见B+树，这里只说一些重点，浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包括几个数据项(深蓝色所示)和指针(黄色所示)，如磁盘块1包括数据项17和35，包括指针P1、P2、P3，P1暗示小于17的磁盘块，P2暗示在17和35之间的磁盘块，P3暗示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点只不存储真实的数据，只存储指引搜刮偏向的数据项，如17、35并不真实存在于数据表中。

b+树的查找进程

（编辑：河北网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!