首页 / MYSQL / Mysql的索引机制一

Mysql的索引机制一

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Mysql的索引机制一，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4189字，纯文字阅读大概需要6分钟。

内容图文

索引的出现是为了提高查询效率，Mysql索引是B+tree

目录

一、索引的常见数据结构
二、InnoDB的索引模型
三、索引的维护
四、名词与相关概念解释

一、索引的常见数据结构

  • 哈希表：
    以键值对存储数据的结构，缺点会发生hash突出，后面跟着的链表和数组，使得哈希表结构适用于等值查询的场景。

  • 二叉树：
    二叉树是搜索效率最高的，时间复杂度是 O(log(N))，为了维持 O(log(N)) 的查询复杂度，得保持这颗树是一颗平衡二叉树。

  • B+树：
    但索引不止存在内存中，还要写到磁盘上。二叉树的深度比较深，读取磁盘需要时间，所有引出了N叉树降低磁盘访问开销。

返回顶部目录

二、InnoDB的索引模型

  • InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的

  • 每一个索引在 InnoDB 里面对应一棵 B+ 树

  • 假设，我们有一个主键列为 ID 的表，表中有字段 value，并且在 value上有索引。

    mysql> create table T
(id int primary key,
 value int not null, 
 name varchar(16),
 index (value)
 )engine=InnoDB;

    表中 R1~R5 的 (ID,value) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)，两棵树的示例示意图如下。
    Mysql的索引机制一 - 文章图片

    • 根据叶子节点的内容，索引类型分为主键索引和非主键索引。

    • 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。

    • 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

    • 例子：主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。根据上面的索引结构说明，我们来讨论一个问题：基于主键索引和普通索引的查询有什么区别？如果语句是 select * from T where ID=500，即主键查询方式，则只需要搜索 ID 这棵 B+ 树；如果语句是 select * from T where value=5，即普通索引查询方式，则需要先搜索 value 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

返回顶部目录

三、索引的维护

  • 在上面的表中，如果新插入的行ID值为400,需要逻辑上挪动后面的数据，空出位置。
  • 如果那个数据页数据满了，根据 B+ 树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。在这种情况下，性能自然会受影响。
  • 基于上面的问题，我们在很多建表规范中，都有这样的描述，建表需要一定要有自增主键。
    • 每次插入一条新记录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。
    • 而有业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高。
  • 由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号等做主键，那么每个二级索引的叶子节点占用约 20 个字节，而如果用整型做主键，则只要 4 个字节，如果是长整型（bigint）则是 8 个字节。主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。
  • 业务字段直接做主键的（典型的kv场景）,可以避免每次查询需要回表搜索两棵树：
    • 只有一个索引；
    • 该索引必须是唯一索引。

返回顶部目录

名词与相关概念解释

  • 为什么数据库存储使用b+树 而不是二叉树？

    • 因为二叉树树高过高，每次查询都需要访问过多节点，即访问数据块过多，而从磁盘随机读取数据块过于耗时。
    • 一页就是B-tree上的一个节点,因为根节点总是在内存,所以查找一个值最多进行树高h-1次磁盘io就能找到。
    • 虽然平衡二叉树时间复杂度低，但树深度可能较深，每一个层级的访问都伴随着磁盘的访问。

  • 为什么 “N 叉”树中的“N”取决于数据块的大小？

    • 一个数据块假如有500 字节，一个子节点的索引地址大小是10个字节，那么这个节点就可以存储50个孩子节点的索引，这个树就是50叉树，所以 N取决于数据块的大小。

  • 为什么 InnoDB整数字段索引的b+树最大能维持大约1200叉树

    • MySql默认一个节点的长度为16K，一个整数（bigint）字段索引的长度为 8B,另外每个索引还跟着6B的指向其子树的指针；所以16K/14B ≈ 1170

  • 比较新的数据结构

    • redis 中使用到跳表，hbase memstore 和flink中的rocksdb使用到LSM树

  • 关于 InnoDB 的表结构：

    • 1.在 InnoDB 中，每一张表其实就是多个 B+ 树，即一个主键索引树和多个非主键索引树。 2.执行查询的效率，使用主键索引 > 使用非主键索引 > 不使用索引。 3.如果不使用索引进行查询，则从主索引 B+ 树的叶子节点进行遍历。

  • 回表：

    • 主键索引的b+树的叶子节点存储的是具体的行数据，非叶子节点存储的是主键的值。叶子节点之间通过链表连接 非主键索引的叶子节点存储的是主键的值，所以通过非主键索引查询数据时，先找到主键，再去主键索引上根据主键找到具体的行数据

  • 根据具体需求选择合适的结构

    • 二叉树也会畸变成单链表，所以才有了AVL树通过旋转的方式来维持树的平衡，但后来发现大量的旋转实在是性能不好，所以有了红黑树。都是二叉树，只是约束条件不一样。没有最好的方法只有更适合的方法，要维持某一方面的优势需要牺牲另一方面的优势，就看如何选择了。

内容总结

以上是互联网集市为您收集整理的Mysql的索引机制一全部内容，希望文章能够帮你解决Mysql的索引机制一所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/857632.html

来源：【匿名】