查看代码测试

索引

参考
参考

了解索引(索引概念)

  1. 索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分),它们包含着对数据表里所有记录的引用指针。
  2. 索引是一种数据结构。数据库索引,是数据库管理系统中一个排序的数据结构,以协助快速查询、更新数据库表中数据。索引的实现通常使用B数及其变种B+数。
  3. 更通俗的说,索引就相当于目录。为了方便查找书中的内容,通过对内容建立索引形成目录。索引是一个文件,它是要占据物理空间的。

mysql索引的数据结构以及分类

类似问题: 数据库索引结构是什么样的(我回答B+树,然后问对磁盘有什么优势夺命追问,我说降低IO次数,问为什么)
类似问题: 数据库使用b+树的好处
类似问题: b+树的特性,为啥要用到这
类似问题: B+ Tree
类似问题: 谈谈索引的数据结构?说了 B+树
类似问题: B+树和 B-树的区别以及优点?
类似问题: 为什么不用搜索树?
类似问题: B+树的特点
类似问题: mysql 索引 2次
类似问题:mysql索引结构。

从数据结构的角度看,常用的索引可以分为full-text索引,hash索引,b+树索引:MjiiVj

在创建表时,InnoDB 存储引擎默认使用表的主键作为主键索引,该主键索引就是聚簇索引(Clustered Index),如果表没有定义主键,InnoDB 就自己产生一个隐藏的 6 个字节的主键 ID 值作为主键索引,而创建的主键索引默认使用的是 B+Tree 索引。

B+Tree 相比于 B 树和二叉树来说,最大的优势在于查询效率。

B+树和B树的明显区别:

  1. +树的叶子节点从左到右都是链接起来的,并且从左到右依次增大。解决了这个回旋查找的问题,这也是为什么我们排序的时候最好使用索引排序,因为索引帮助我们排好序了。
  2. B+树中非叶子节点的key都会在叶子节点中可以找到的,B+树非叶子节点只存储key,不存储value。叶子节点既存key又存value,value是对应数据的地址。在B树中,每个节点的value保存的是对应数据的地址。所以 B+Tree 的单个节点的数据量更小,在相同的磁盘 I/O 次数下,就能查询更多的节点。

那么问题来了,如果你当前查询数据时候,不是通过主键 ID,而是用商品编码查询商品,那么查询过程又是怎样的呢?

通过非主键(辅助索引)查询商品数据的过程:如果你用商品编码查询商品(即使用辅助索引进行查询),会先检索辅助索引中的 B+Tree 的 商品编码,找到对应的叶子节点,获取主键值,然后再通过主键索引中的 B+Tree 树查询到对应的叶子节点,然后获取整行数据。这个过程叫回表。以上就是索引的实现原理。

如果你被问到“为什么 MySQL 会选择 B+Tree 当索引数据结构?”其实在考察你两个方面: B+Tree 的索引原理; B+Tree 索引相比于其他索引类型的优势。

我们刚刚已经讲了 B+Tree 的索引原理,现在就来回答一下 B+Tree 相比于其他常见索引结构,如 B 树、二叉树或 Hash 索引结构的优势在哪儿?

B+Tree 相对于 B 树 索引结构的优势

  1. B+Tree 只在叶子节点存储数据,而 B 树 的非叶子节点也要存储数据,所以 B+Tree 的单个节点的数据量更小,在相同的磁盘 I/O 次数下,就能查询更多的节点。
  2. 另外,B+Tree 叶子节点采用的是双链表连接,适合 MySQL 中常见的基于范围的顺序查找,而 B 树无法做到这一点。
  3. B树在同样节点个数的情况下可以做到更低的树高 ,解决了树的高度的问题,更低的树高对应更低的磁盘IO次数。但是B树也是存在回旋查找(往回找)问题的,比如,这里要查找大于5的,vp5rxv 如果问到为什么可以降低IO次数,可以看该B树存储的图:R94YCm

B+Tree 相对于二叉树索引结构的优势

  1. 对于有 N 个叶子节点的 B+Tree,其搜索复杂度为O(logdN),其中 d 表示节点允许的最大子节点个数为 d 个。在实际的应用当中, d 值是大于100的,这样就保证了,即使数据达到千万级别时,B+Tree 的高度依然维持在 34 层左右,也就是说一次数据查询操作只需要做 34 次的磁盘 I/O 操作就能查询到目标数据(这里的查询参考上面 B+Tree 的聚簇索引的查询过程)。
  2. 而二叉树的每个父节点的儿子节点个数只能是 2 个,意味着其搜索复杂度为 O(logN),这已经比 B+Tree 高出不少,因此二叉树检索到目标数据所经历的磁盘 I/O 次数要更多。

但是实际上大多数的数据库存储却并不使用二叉树。其原因是:索引不止存在内存中,还要写到磁盘上。你可以想象一下一棵 100 万节点的平衡二叉树,树高 20。一次查询可能需要访问 20 个数据块。在机械硬盘时代,从磁盘随机读一个数据块需要 10 ms 左右的寻址时间。也就是说,对于一个 100 万行的表,如果使用二叉树来存储,单独访问一个行可能需要 20 个 10 ms 的时间,这个查询可真够慢的。

为了让一个查询尽量少地读磁盘,就必须让查询过程访问尽量少的数据块。那么,我们就不应该使用二叉树,而是要使用“N 叉”树。这里,“N 叉”树中的“N”取决于数据块的大小。

以 InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。这棵树高是 4 的时候,就可以存 1200 的 3 次方个值,这已经 17 亿了。考虑到树根的数据块总是在内存中的,一个 10 亿行的表上一个整数字段的索引,查找一个值最多只需要访问 3 次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。

B+Tree 相对于 Hash 表存储结构的优势

  1. 我们知道范围查询是 MySQL 中常见的场景,因为hash的值是无序的,因为无序就不能进行范围查找。所以Hash 表不适合做范围查询,它更适合做等值的查询,这也是 B+Tree 索引要比 Hash 表索引有着更广泛的适用场景的原因。
  2. 还有就是我们排序的时候无法根据hash值进行排序,因为hash值是无序的。
  3. 还有的就是hash冲突可能造成性能退化到O(N)

总结:至此,你就知道“为什么 MySQL 会选择 B+Tree 来做索引”了。在回答时,你要着眼于 B+Tree 的优势,然后再引入索引原理的查询过程(掌握这些知识点,这个问题其实比较容易回答)。

B+Tree 相对于 AVL树存储结构的优势
avl树查找的话,查找速度随着高度增加会越来越慢。还有一个致命缺点:比如查找大于某一个值的数据,我们不仅仅在该值对应的右节点比他大,还要往回找。比如下图中查找大于6的:B7sQNe

B+Tree 相对于 平衡二叉树树存储结构的优势

B树相对于平衡二叉树的不同是,每个节点包含的关键字增多了,特别是在B树应用到数据库中的时候,数据库充分利用了磁盘块的原理(磁盘数据存储是采用块的形式存储的,每个块的大小为4K,每次IO进行数据读取时,同一个磁盘块的数据可以一次性读取出来)把节点大小限制和充分使用在磁盘快大小范围;把树的节点关键字增多后树的层级比原来的二叉树少了,减少数据查找的次数和复杂度;

总结:

  1. B+树彻底解决了这个回旋查找的问题,
    V5BEGA
    pnhZeZ
  2. 如上图所示的B+树中,我们可以发现,B+树的所有非叶子节点最终都会存在叶子节点。

B+Tree 相对于有序数组的优势
如果仅仅看查询效率,有序数组就是最好的数据结构了。但是,在需要更新数据的时候就麻烦了,你往中间插入一个记录就必须得挪动后面所有的记录,有序数组索引只适用于静态存储引擎

参考:https://zhuanlan.zhihu.com/p/140876416

参考:知乎文章

聚簇索引,是每一个叶子节点最终都保留了一整行的记录信息,不需要进行回表,直接可以查找到
但是非聚簇索引是每一个叶子节点都保留对应的主键值,通过主键进行回表来获取对应的记录信息,需要查两次

别人的:
这个问题会涉及到mysql的存储数据结构,B+tree
多叉搜索树,有序,类似二叉搜索树(特性:中序遍历是有序的);curd的时间复杂度都是logN;
再谈谈mysql的索引结构,innodb引擎中分主键(聚簇索引)索引树和二级索引树;
Innodb的主键索引树的叶子节点上存储行数据,非叶子结点只存储主键id,简单讲就是聚簇索引相当于物理内存地址(一级指针),查询快;
而二级索引树的每个节点只会存储索引字段值和主键id;
2种索引查询对比:
主键索引树:主键id=>叶子结点row数据
二级索引树: 二级索引树上找到对应的id=>主键索引树上的id=>主键索引树上的叶子结点行记录

上面“二级索引树=>主键索引树”的过程叫做“回表”,可以通过“索引覆盖”,“索引下推”优化

索引优化

对于执行计划,参数有 possible_keys 字段表示可能用到的索引,key 字段表示实际用的索引,key_len 表示索引的长度,rows 表示扫描的数据行数。

这其中需要你重点关注 type 字段, 表示数据扫描类型,也就是描述了找到所需数据时使用的扫描方式是什么,常见扫描类型的执行效率从低到高的顺序为(考虑到查询效率问题,全表扫描和全索引扫描要尽量避免):

  1. ALL(全表扫描);
  2. index(全索引扫描);
  3. range(索引范围扫描);
  4. ref(非唯一索引扫描);
  5. eq_ref(唯一索引扫描);
  6. const(结果只有一条的主键或唯一索引扫描)。

总的来说,执行计划是研发工程师分析索引详情必会的技能(很多大厂公司招聘 JD 上写着“SQL 语句调优” ),所以你在面试时也要知道执行计划核心参数的含义,如 type。在回答时,也要以重点参数为切入点,再扩展到其他参数,然后再说自己是怎么做 SQL 优化工作的。

常见索引优化方法

  1. 前缀索引优化:前缀索引就是用某个字段中,字符串的前几个字符建立索引,比如我们可以在订单表上对商品名称字段的前 5 个字符建立索引。使用前缀索引是为了减小索引字段大小,可以增加一个索引页中存储的索引值,有效提高索引的查询速度。在一些大字符串的字段作为索引时,使用前缀索引可以帮助我们减小索引项的大小。但是,前缀索引有一定的局限性,例如 order by 就无法使用前缀索引,无法把前缀索引用作覆盖索引。
  2. 覆盖索引优化:覆盖索引是指 SQL 中 query 的所有字段,在索引 B+tree 的叶子节点上都能找得到的那些索引,从辅助索引中查询得到记录,而不需要通过聚簇索引查询获得。假设我们只需要查询商品的名称、价格,有什么方式可以避免回表呢?我们可以建立一个组合索引,即商品ID、名称、价格作为一个组合索引。如果索引中存在这些数据,查询将不会再次检索主键索引,从而避免回表。所以,使用覆盖索引的好处很明显,即不需要查询出包含整行记录的所有信息,也就减少了大量的 I/O 操作。
  3. 联合索引:联合索引时,存在最左匹配原则,也就是按照最左优先的方式进行索引的匹配。比如联合索引 (userpin, username),如果查询条件是 WHERE userpin=1 AND username=2,就可以匹配上联合索引;或者查询条件是 WHERE userpin=1,也能匹配上联合索引,但是如果查询条件是 WHERE username=2,就无法匹配上联合索引。另外,建立联合索引时的字段顺序,对索引效率也有很大影响。越靠前的字段被用于索引过滤的概率越高,实际开发工作中建立联合索引时,要把区分度大的字段排在前面,这样区分度大的字段越有可能被更多的 SQL 使用到。

区分度就是某个字段 column 不同值的个数除以表的总行数,比如性别的区分度就很小,不适合建立索引或不适合排在联合索引列的靠前的位置,而 uuid 这类字段就比较适合做索引或排在联合索引列的靠前的位置。

区分度公式:pRlbc9

总结:
sRgeTB

数据库中数据很多的时候如何处理?面试官提示了索引

索引越多越好么?

不一定,通常,通过索引查询数据比全表扫描要快。但是我们也必须注意到它的代价。
索引需要空间来存储,也需要定期维护, 每当有记录在表中增减或索引列被修改时,索引本身也会被修改。 这意味着每条记录的INSERT,DELETE,UPDATE将为此多付出4,5 次的磁盘I/O。 因为索引需要额外的存储空间和处理,那些不必要的索引反而会使查询反应时间变慢。使用索引查询不一定能提高查询性能,索引范围查询(INDEX RANGE SCAN)适用于两种情况:

  1. 基于一个范围的检索,一般查询返回结果集小于表中记录数的30%
  2. 基于非唯一性索引的检索
    查找过程可以理解为:最左匹配原则
    参考
    内部也是一棵B+树:参考

    如何创建索引

    mysql 索引慢分析(线上开启slowlog,提取慢查询,然后仔细分析explain 中 type字段以及extra字段,发生的具体场景及mysql是怎么做的,被表扬回答的不错)

    了解Mysql中的索引:涉3树是这样的一颗多路查找树,其中每一个节点都具有两个孩子及到什么是B树,与二叉搜索树和平衡二叉树区别,以及B+树区别

    InnoDB二级索引流程

    主键和索引的区别

    如何提高索引的速度

    innodb的索引有哪些

    联合索引的使用原则

    联合索引在b树,b+树的结构是怎么样的,查找过程你了解过么

    数据库聚集索引和辅助索引(也就是非聚簇索引)

    何时使用索引

    索引是如何实现的?多种引擎的实现区别?聚族索引,非聚族索引,二级索引,唯一索引、最左匹配原则等等(非常重要)

    上面“二级索引树=>主键索引树”的过程叫做“回表”,可以通过“索引覆盖”,“索引下推”优化

    数据库覆盖索引

    假设我们有张表,结构如下:

create table user( id int(11) not null, age int(11) not null, primary key(id), key(age) );

覆盖索引指的是在一次查询中,如果一个索引包含或者说覆盖所有需要查询的字段的值,我们就称之为覆盖索引,而不再需要回表查询。

而要确定一个查询是否是覆盖索引,我们只需要explain sql语句看Extra的结果是否是“Using index”即可。

以上面的user表来举例,我们再增加一个name字段,然后做一些查询试试。

explain select * from user where age=1; //查询的name无法从索引数据获取 explain select id,age from user where age=1; //可以直接从索引获取

评论