「索引的概念」: 索引是一种特殊的文件(InnoDB 数据表上的索引是表空间的一个组成部分), 它们包含着对数据表里的所有记录的引用指针. 通俗来说就是数据库索引就好像是一本书的目录, 能够加快数据库的查询速度.
哈喽大家好! 我是小三. 今天我们来讲索引.
索引是什么?
「索引的概念」: 索引是一种特殊的文件(InnoDB 数据表上的索引是表空间的一个组成部分), 它们包含着对数据表里的所有记录的引用指针. 通俗来说就是数据库索引就好像是一本书的目录, 能够加快数据库的查询速度.
「索引的作用」: 索引存在的目的就是在于提高查询效率, 使得原始的随机全表扫描变成了快速顺序锁定数据
常用的索引分类:
1, 普通索引: 这是最基本的索引, 没有任何的限制
2, 唯一索引: 引列的值必须唯一, 但允许有空值(注意和主键不同)
3, 组合索引: 多个数据列组成的索引, 遵守了最左匹配原则
索引高性能保证:
1, 把查询过程中的随机事件变成了顺序事件
2, 数据保存在磁盘上, 而为了提高性能, 每次又可以把一部分的数据读入内存来计算, 访问磁盘的成本大概是访问内存的十万倍左右.
3, 考虑到磁盘 IO 是非常高昂的操作, 计算机操作系统做了一系列的优化, 当进行一次 IO 时, 不光把当前磁盘的地址的数据也把相邻的数据也都读取到内存的缓冲区之内. 因为局部的预读性原理告诉了我们, 当计算机访问一个地址的数据的时候, 与它响铃的数据也会很快被访问到. 每一次 IO 读取的数据我们都称之为一页(page). 具体一页会有多大的数据, 这跟操作系统有关, 一般为 4k 或者是 8k.
那为什么磁盘读取数据会很慢呢?
我们知道磁盘读取时间 = 寻道时间 + 旋转时间 + 传输时间, 当需要从磁盘读取到数据的时候, 系统会将数据的逻辑地址传给磁盘, 磁盘的控制电路按照寻址逻辑将逻辑地址翻译成了物理地址, 就确定了要读的数据 在哪一个磁道, 哪个扇区. 为了读取扇区的数据, 需要将磁头放到扇区的上方, 为了实现这一点, 磁头需要移动对准相应的磁道, 这个过程叫寻道, 在这里所耗费的时间叫做寻道时间, 然后磁盘旋转目标扇区旋转到磁头下, 这个过程耗费的时间叫做旋转时间.
索引的底层实现方案
我们使用索引的目的, 自然是要提高查询的效率. 例如像字典, 如果要查询 "mysql" 这个单词, 我们首先肯定是要定位到 m 字母, 然后从下往下找到 y 字母, 以此类推.
索引的设计难度
查询要求: 等值查询, 还有范围查询(>,<,between,in), 模糊查询(like), 并集查询(or)
数据量: 超过一千万数据通过索引查询, 查询性能保证
常见的检索方案分析
顺序检索: 最基本的查询算法 - 复杂度 O(n), 数据量大的话这个算法的效率是糟糕的
二叉树查找: O(log2n), 单层节点所能存储数据量较少, 需要进行遍历多层才能拿到数据, 总结点数 k 与高度 h 的关系为 k=(2^h)-1
hash 索引: 无法满足范围查找, 但是它的等值检索快, hash 值 ==》物理地址 x018, 范围检索
B-Tree: 每个节点都是一个二元数组:[key,data], 所有的节点都可以存储数据, key 为索引 key,data 为除之外的数据
B+Tree 数据结构高性能解析
B-Tree 的缺点: 插入删除新的数据记录会破坏掉 B-Tree 的性质, 因此在插入删除时, 需要对树进行一个分裂, 合并, 转移等操作来保持 B-Tree 的性质. 在区间查找时可能需要返回上层节点重新, IO 操作繁琐.
B+Tree 的改进: 非叶子节点不存储 data, 只存储了索引的 key, 只有叶子节点才存储 data
「高性能的保证」:
第一, 3 层的 b + 树可以表示上百万的数据, 如果上百万的数据查找只需要进行三次 IO 的话, 那么对性能的提高无疑是巨大的, 如果没有索引的话, 每个数据项都要发生一次 IO 那么就会有百万次的 IO, 这显然成本非常非常高.
第二, 在 B+Tree 的每个叶子节点增加一个指向相邻子节点的指针, 这样就形成了带有顺序访问指针的 B+Tree
第三, B+Tree 只在叶子节点来存储数据, 所有的叶子节点包含一个链指针, 其他内存的非叶子节点只存储索引数据. 只利用索引快速的定位数据索引范围, 先定位索引再通过索引高效的定位数据.
MySQL 为什么会选错索引
优化器的逻辑
MySQL Server 层的优化器负责的是选择索引, 而优化器选择索引的目的就是要找到一个最优的执行方案, 并且用最小代价来执行语句. 在数据库里面, 扫描行数是影响执行代价的因素之一. 扫描的行数越少, 也就意味着访问的磁盘的数据次数就越小, 消耗的 CPU 就越少. 扫描行数并不是唯一的判断标准, 优化器还会结合了是否使用临时表, 是否排序等等因素来综合判断.
扫描行数是怎么判断的
MySQL 在真正开始执行语句之前, 并不可以精确的知道满足该查询条件的记录究竟有多少条, 只能根据统计的信息来估算记录数. 所以这个统计信息就是索引的 "区分度". 显然, 一个索引上面的值不同得越多, 这个索引的区分度就越好. 在一个索引上不同值的个数, 称为基数.
那么, MySQL 是怎么样得到索引基数的? 在这里 MySQL 采样统计方法, 但是为什么要使用采样统计这种方法呢? 原因就是因为如果把整张表取出来然后进行一行行的统计, 虽然这样能够得到精确的数据, 但是代价也太高了, 所以的话只能使用采样统计.
- # 创建表
- CREATE TABLE `test` (
- `id` int(11) NOT NULL,
- `a` int(11) NOT NULL default 0,
- `b` int(11) NOT NULL default 0,
- PRIMARY KEY (`id`),
- KEY `a` (`a`),
- KEY `b` (`b`)
- ) ENGINE=InnoDB;
- # 添加数据
- delimiter ;;
- create procedure xddata()
- begin
- declare i int;
- set i=1;
- while(i<=100000)do
- insert into test values(i, i, i);
- set i=i+1;
- end while;
- end;;
- delimiter ;
- call xddata();
数据查询
explain select * from test where (a between 1000 and 2000) and (b between 50000 and 100000) order by b limit 1;
「为什么会出现这种结果呢?」
在多个的索引情况下, 优化器一般会通过比较了扫描行数, 是否需要临时表以及是否需要排序等因素来作为索引的半段依据.
选择了索引 b, 则就需要在 b 索引上扫描 9W 条记录, 然后回到主键索引上过滤掉不满足 a 条件的记录, 因为索引有序, 所以使用 b 索引不需要额外排序.
「解决方案」
使用 force index a 让 MySQL 直接选择 a 索引来处理此处的查询
- select * from test where (a between 1000 and 2000) and (b between 50000 and 100000) order by b limit 1;
- select * from test force index(a) where (a between 1000 and 2000) and (b between 50000 and 100000) order by b limit 1;
在其他的场景:
数据表有频繁的删除或者是更新操作导致的数据空洞造成的, 造成的原因可能是分析器 explain 的结果预估的 rows 值跟实际的情况差距比较大, 分析器分析扫描行数用的是抽样调查. 统计分析不对话可以使用 analyze table test 命令, 用来重新统计索引信息.
[面试题] 唯一索引和普通索引的区别在哪?
「1. 查询上的区别」
对唯一索引, 由于索引定义了唯一性, 查到第一个满足条件的记录之后, 就会停止检索.
对普通索引, 查找到满足条件的第一个记录'ab'后, 需要找下个记录, 直到碰到第一个不满足 k='ab'条件的记录
「2. 修改上的区别」
对于唯一索引, 所有更新操作要先判断该操作是否会违反唯一性约束, 唯一索引不会用 change buff, 若所修改的数据在内存当中, 找到索引所对应的存储位置, 判断到没有冲突, 然后再插入值, 语句执行结束. 若所修改的数据不在内存当中, 则需要将数据页也读入内存, 判断到没有冲突, 再插入值, 语句执行结束.
「3. 性能上的区别」
普通索引查找数据的时候会将符合条件的都给查找出来
唯一索引主要是第一条符合条件的就会立即返回, 不会在继续查找了, 因为唯一的为数已经确保了只有一条符合条件
来源: http://database.51cto.com/art/202201/697977.htm