乐趣区

关于后端:详谈-MySQL-索引B树的原理以及创建索引的几大原则

jiezi

明天应做的事没有做，今天再早也是耽搁了。

一、存储引擎的比拟

注：下面提到的 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 索引有个大体的理解。

接下来咱们先看看 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- 树是开区间）；
  4. 为所有叶子结点减少一个链指针；
  5. 所有关键字都在叶子结点呈现；

如：（M=3）

B+ 的搜寻与 B - 树也基本相同，区别是 B + 树只有达到叶子结点才命中（B- 树能够在非叶子结点命中），其性能也等价于在关键字选集做一次二分查找；

B+ 的个性：

  1. 所有关键字都呈现在叶子结点的链表中（浓密索引），且链表中的关键字恰好是有序的；
  2. 不可能在非叶子结点命中；
  3. 非叶子结点相当于是叶子结点的索引（稠密索引），叶子结点相当于是存储（关键字）数据的数据层；
  4. 更适宜文件索引零碎；

三、创立索引的几大准则

1. 最左前缀匹配准则，十分重要的准则，mysql 会始终向右匹配直到遇到范畴查问 (>、<、between、like) 就进行匹配，比方 a = 1 and b = 2 and c > 3 and d = 4 如果建设 (a,b,c,d) 程序的索引，d 是用不到索引的，如果建设 (a,b,d,c) 的索引则都能够用到，a,b,d 的程序能够任意调整。

2.= 和 in 能够乱序，比方 a = 1 and b = 2 and c = 3 建设 (a,b,c) 索引能够任意程序，mysql 的查问优化器会帮你优化成索引能够辨认的模式

3. 尽量抉择区分度高的列作为索引, 区分度的公式是 count(distinct col)/count(*)，示意字段不反复的比例，比例越大咱们扫描的记录数越少，惟一键的区分度是 1，而一些状态、性别字段可能在大数据背后区分度就是 0，那可能有人会问，这个比例有什么经验值吗？应用场景不同，这个值也很难确定，个别须要 join 的字段咱们都要求是 0.1 以上，即均匀 1 条扫描 10 条记录

4. 索引列不能参加计算，放弃列“洁净”，比方 from_unixtime(create_time) =’2014-05-29’就不能应用到索引，起因很简略，b+ 树中存的都是数据表中的字段值，但进行检索时，须要把所有元素都利用函数能力比拟，显然老本太大。所以语句应该写成 create_time = unix_timestamp(’2014-05-29’);

5. 尽量的扩大索引，不要新建索引。比方表中曾经有 a 的索引，当初要加 (a,b) 的索引，那么只须要批改原来的索引即可

退出移动版