索引介绍、索引原理、索引的数据结构(二叉排序树、平衡二叉树、B树、B+树)_索引数据结构

引入

本篇博客偏理论, 将会介绍一下知识:

• 索引介绍
• 索引原理
• 索引的数据结构(二叉树—>平衡二叉树—>B树—>B+树)
• 聚集索引与辅助索引
• MySQL索引管理
• 创建和删除索引的语法
• 创建索引后的测试 (查询速度的变化)
• 如何正确使用索引
• 回表
• 覆盖索引
• 联合索引
• 最左前缀匹配
• 索引下推
• MySQL查询优化 : explain
• 慢查询优化的基本步骤
• 慢日志管理

一.索引介绍

1.什么是索引

• 索引是对数据库表中一列或多列的值进行排序的一种数据结构, 使用索引可以快速访问数据库表中的特定信息
• 为数据库建立索引, 就好比为书建立目录

2.为什么要有索引

• 优化数据查询效率

数据库的数据一般存储在磁盘中, 相比较内存, 磁盘的访问速度较慢索引就是可以帮助数据库快速从磁盘中找到数据的一种数据结构

• 注意 : 创建索引后会降低增、删、改的效率

虽然会降低, 但是一般的应用系统，读写比例在10:1左右，而且插入操作和一般的更新操作很少出现性能问题，遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，所以查询语句的优化显然是重中之重

3.为表创建的索引是不是越多越好?

• 多数情况下, 我们知道索引能够提高查询效率, 但过多也会影响应用程序效率, 怎么加才是关键
• 一个应用程序的设计, 数据上过多或过少的索引都会引发应用程序的效率问题, 所以我们需要找到一个平衡点
• 当表有大量数据的情况下, 创建索引的速度会很慢, 并且对于写的性能也会大幅度降低

4.索引应该什么时候加才最合适

• 任何一个软件都有其吸引用户的亮点, 亮点背后对应的是热数据, 无疑开发人员对热数据的所对应的数据库字段有哪些, 应该在开发软件的过程中就提前为相应的字段加上索引, 而不是等软件上线后让DBA发现慢查询sql后再做处理

原因 :

1.一个软件慢会影响用户体验, 但是慢的原因有很多, 你不能立即确定就是 SQL 的问题, 当你定位到 SQL 问题的时候就已经过去很久了, 问题没有得到及时的解决

2.大多数DBA都是管理型DBA而非开发型, 所以即便是DBA从日志中看到了慢查询sql, 也会因为其不懂业务而很难分析出慢的原因

二.索引原理

1.索引的原理

• 通过不断的缩小想要查询的数据范围筛选出最终的结果

就比如买火车票(无索引) : 如果没有12360火车票订购软件, 摆在我们面前的就是成千上万辆火车, 选择那一辆的条件有火车类型、出发和终点、时间等等, 我们需要一辆一辆火车去比对自己的筛选条件, 运气好第一辆就是要找的火车, 运气不好第一千辆才是要找的火车

加入索引 : 现在我们只需要在12360软件上选择高铁, 就能筛选掉不是高铁的火车, 缩小了查询范围; 再输入出发点和终点, 又缩小了查询范围; 再输入时间, 范围又减少, 最终找到自己需要的车次, 由不固定查询次数变成很小的固定查询次数

2.磁盘I/O与预读

• I\O延迟

IO延迟 = 平均寻道时间 + 平均延迟时间(一般为9ms)—>例子:假设当前硬盘转轴(盘片)转速是7200/min，也就是120/s，那么转一圈需要花费1/120≈8ms，半圈也就是4ms(假设找到数据要半圈)

9ms左右对于我们来讲很短, 但对于一台500-MIPS的机器来说每秒可以执行5亿条指令, 换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间, 这简直是场灾难

• 预读

考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助

三.索引的数据结构

索引的数据结构是 B+树, 而 B+树 是经过 二叉排序树 到 二叉平衡树 再到 B树 最后到 B+树 演变过来的, 下面简单介绍一下:

1.二叉排序树(二叉查找树)

• 顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点(就是最下面一排)

对于一列数字 : 5、6、7、8、9、10

• 如果我们需要找到 key=9 的节点, 先将 9 与根节点比较, 大于根节点, 于是往右边找; 继续与右边的 10 比较, 小于, 于是往左边找, 正好找到九

利用二叉排序树我们只需要3次即可找到匹配的数据; 如果在数字列中一条条的查找的话，我们需要5次才能找到

2.平衡二叉树(AVL树)

• 平衡二叉树可以说是二叉排序树的改进版, 是特殊的二叉排序树

上面我们讲解了利用二叉排序树可以快速的找到数据; 但是，如果上面的二叉排序树是这样的构造：

平均查找长度是3, 如果我们调整一下关键字的序列

调整之后平均查找长度是 2.2, 从上面我们可以看出平均查找长度与数的高度有关, 平均查找长度越小, 查找速度就越快, 所以我们应该尽可能的让这棵树矮

• 怎么判断一颗二叉树是否是平衡二叉树?

这里引入了平衡因子的概念, 左子树的高度减右子数的高度就是平衡因子, 平衡因子的绝对值小于或等于一就是平衡二叉树, 大于一就是非平衡二叉树, 如下图平衡因子为 4 就是非平衡二叉树

我们调整一下关键字序列, 各子数平衡因子绝对值都小于或等于 1, 那么这就是一颗平衡二叉树

3.B 树 ( Balanced Tree）多路平衡查找树

• 我们知道平衡二叉树每个节点只能存储一个键值和数据

如果我们要存储海量的数据呢？可以想象到二叉树的节点将会非常多，高度也会及其高，我们查找数据时也会进行很多次磁盘IO，我们查找数据的效率将会极低

• 为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树, 也就是 B树

从上图可以看出，B树相对于平衡二叉树，每个节点(B树中节点称之为页)存储了更多的键值(key)和数据(data)，并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的B树为3阶B树，高度也会很低。 基于这个特性，B树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多

假设每个节点可以储存两个值(不代表只能存两个), 我们找到75:

• 先与 页1 比较,在 35 右边找到 p3指针 定位到 页4
• 与 页4 中的索引对比, 在 65-87 之间, 找到指针 p2, 定位到 页10
• 与 页10 中的索引对比, 找到相对应的 75

4.B+ 树

• B+ 树是对 B树的进一步优化

• 通过上图我们来对比下 B+ 树与 B树的不同:

• B+ 树非叶子节点上是不存储数据的，仅存储键值，而 B 树节点中不仅存储键值，也会存储数据

• 之所以这么做是因为在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快

• B+ 树的阶数是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。

• 一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO

• 3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要两次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高

• B+ 树的两种性质

• 索引字段要尽量的小 : 磁盘块的大小也就是一个数据页的大小，是固定的. 如果数据项占的空间越小，数据项的数量越多，树的高度就越低, 查询过的IO次数就越少. 这就是为什么每个数据项，即索引字段要尽量的小，比如int占4字节，要比bigint8字节少一半。这也是为什么b+树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降, 下降则会导致每层可存储的数据就少, 因为磁盘块是固定的, 从而要增加层次, 进而导致树增高, 树增高意味着找到底层数据的IO次数增多, 导致查询速度大幅度下降
• 索引的最左匹配特性 : 当b+树的数据项是复合的数据结构，比如(name,age,sex)的时候，b+数是按照从左到右的顺序来建立搜索树的. 比如当(张三,20,F)这样的数据来检索的时候，b+树会优先比较name来确定下一步的所搜方向，如果name相同再依次比较age和sex，最后得到检索的数据. 但当(20,F)这样的没有name的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询。 比如当(张三,F)这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性

5.总结 B+ 树优点

• 在二叉树、平衡二叉树、B树的基础上做了进一步优化, 只有叶子节点放真正的数据，这意味着在等量数据的前提下,B+树的高度是最低的
• B+的叶子节点都是排好序的，这意味着在范围查询上，B+树比B树更快，快就快在一旦找到一个树叶节点，就不需要在再从树根查起了