如何实现MySQL的索引

MySQL中索引分三类：B+树索引、Hash索引、全文索引。InnoDB存储引擎中用的是B+树索引。要介绍B+树索引，不得不提二叉查找树、平衡二叉树和B树这三种数据结构。B+树是从它们三个演化来的。

二叉查找树：

图中为user表建立了一个二叉查找树的索引。节点中存储了键（key）和数据（data）。数据对应user表中的行数据。

如果查找id=12的用户信息，流程如下：
1）将根节点作为当前节点，12大于10，将10的右子节点（13节点）作为当前节点。
2）12与13比较，将13的左子节点（12节点）作为当前节点。
3）12与12比较，满足条件，从当前节点去除data，即id=12，name=xm。
利用二叉查找树，3次可找到匹配数据。如果在表中一条一条查找，需要6次。

平衡二叉树：

如果上面的二叉树这样构造：

变成了一个链表，查询id=17的用户信息，需要查7次，相当于全表扫描。导致这个现象是因为二叉查找树不平衡了。为了解决这个问题，需要用平衡二叉树。
平衡二叉树又称 AVL 树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过 1。

B树：
因为内存的易失性，一般会将数据和索引存储到磁盘中。和内存比，从磁盘读数据会慢很多，所以应当减少读取次数。此外，从磁盘读数据按照磁盘块来读取，而非一条一条的读。
如果我们能把尽可能多的数据放进磁盘块中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？
可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低！
为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。

图中的每个节点称为页（就是磁盘块），在MySQL中数据读取的基本单位都是页。每个节点存储了更多的键值和数据。子节点的个数一般称为阶，上述图中B树为3阶B树。
查找id=28的用户信息，

流程如下：

  • 1）先找到根节点也就是页 1，判断 28 在键值 17 和 35 之间，那么我们根据页 1 中的指针 p2 找到页 3。
  • 2）将 28 和页 3 中的键值相比较，28 在 26 和 30 之间，我们根据页 3 中的指针 p2 找到页 8。
  • 3）将 28 和页 8 中的键值相比较，发现有匹配的键值 28，键值 28 对应的用户信息为（28，bv）。

B+树：

B+树是对B树的进化，其不同：

  • 1）B+树非叶子节点不存储数据，仅存储键值，B树则存储键值和数据（为什么这么做？数据库中页的大小是固定的，InnoDB中默认是16KB，如果不存数据，就可以存更多的键值，树的阶数会更大，树就会更矮胖，查找数据进行磁盘IO的次数就会减少，查询效率快）。一般根节点是常驻内存的。
  • 2）B+树索引的所有数据存储在叶子节点，而且数据是按照顺序排列的（使得范围查找、排序查找、分组查找及去重查找很简单，而B树因为数据分散在各个节点，实现这一点很不容易），B+树的叶子节点中的数据通过单向链表连接，各个页之间通过双向链表连接。

过上图可以看到，在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

在 MySQL 中，B+ 树索引按照存储方式的不同分为聚集索引和非聚集索引。

利用聚集索引查找数据：

现在假设我们要查找 id>=18 并且 id<40 的用户数据。

对应的 sql 语句为：

select * from user where id>=18 and id<40;

其中id为主键，具体的查找过程如下：

  • 1）一般根节点常驻内存的，页1已经在内存中了，不用读磁盘，直接内存读取。
  • 在内存中页1查找id>=18 and id<40或者范围值，先找到id=18的键值。从页1找到指针p2，定位到页3。
  • 2）从磁盘中读取页3，然后将页3放入内存中，然后进行查找，可以找到键值18，然后拿到页3中的指针p1，定位到页8。
  • 3）将页8读取到内存中，根据二分查找法定位到键值18, 因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页 8 中的键值依次进行遍历查找并匹配满足条件的数据。
  • 我们可以一直找到键值为 22 的数据，然后页 8 中就没有数据了，此时我们需要拿着页 8 中的 p 指针去读取页 9 中的数据。
  • 4）因为页 9 不在内存中，就又会加载页 9 到内存中，并通过和页 8 中一样的方式进行数据的查找，直到将页 12 加载到内存中，发现 41 大于 40，此时不满足条件。那么查找到此终止。

具体流程图：

利用非聚集索引查找数据：

查找幸运数字为33的用户信息，需要回表。

到此这篇关于如何实现MySQL的索引的文章就介绍到这了,更多相关实现MySQL的索引内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • MySQL索引失效之隐式转换的问题

    目录 常见索引失效: 一.常见索引失效场景 1.条件字段函数操作 2.条件字段运算操作 3.隐式类型转换 4.隐式字符编码转换 二.类型转换 1.字符串转整型 2.时间类型转换 常见索引失效: 1. 条件索引字段"不干净":函数操作.运算操作 2. 隐式类型转换:字符串转数值:其他类型转换 3. 隐式字符编码转换:按字符编码数据长度大的方向转换,避免数据截取 一.常见索引失效场景 root@test 10:50 > show create table t_num\G ******

  • MySQL的索引原理以及查询优化详解

    MySQL的索引原理以及查询优化详解

    目录 一.介绍 1.什么是索引? 2.为什么要有索引呢? 二.索引的原理 一 索引原理 二 磁盘IO与预读 三.索引的数据结构 四.Mysql索引管理 一.功能 二.MySQL的索引分类 三. 索引的两大类型hash与btree 四.创建/删除索引的语法 五.测试索引 1.准备 2 .在没有索引的前提下测试查询速度 3. 加上索引 六.正确使用索引 一.覆盖索引 二.联合索引 三.索引合并 七.慢查询优化的基本步骤 总结 一.介绍 1.什么是索引? 一般的应用系统,读写比例在10:1左右,而且插

  • Mysql的复合索引如何生效

    目录 背景 认识复合索引 最左匹配原则 字段顺序的影响 复合索引可以替代单一索引吗? 小结 背景 最近频繁出现慢SQL导致系统性能问题,于是决定针对索引进行一些优化.一些表结构本身已经有了不少索引,如果再继续添加索引,势必会影响到插入数据的性能.那么,是否可以使用组合索引来达到目的呢?这篇文章咱们来一探究竟. 认识复合索引 如果where条件中使用到多个字段,并且需要对多个字段建立索引,此时就可以考虑采用复合索引(组合索引).比如查询地址时需要输入省.市,那么在省.市上建立索引,当数据量大时会明

  • MySQL的复合索引总结

    目录 1.背景 2.认识复合索引 3.最左匹配原则 4.字段顺序的影响 5.单字段是否可以触发索引? 7.复合索引可以替代单一索引吗? 1.背景 最近频繁出现慢SQL导致系统性能问题,于是决定针对索引进行一些优化.一些表结构本身已经有了不少索引,如果再继续添加索引,势必会影响到插入数据的性能.那么,是否可以使用组合索引来达到目的呢?这篇文章咱们来一探究竟. 2.认识复合索引 如果where条件中使用到多个字段,并且需要对多个字段建立索引,此时就可以考虑采用复合索引(组合索引).比如查询地址时需要

  • mysql数据库之索引详细介绍

    mysql数据库之索引详细介绍

    目录 思维导图 简单理解 索引模型的演变 二叉查找树 自平衡二叉树 B树 B+树 聚集索引与二级索引 总结 如果你想深入了解为什么mysql可以快速的进行检索数据,那么你一定要来了解一下mysql的索引原理 思维导图 简单理解 你可以把索引理解为一本书的目录,我们可以通过索引快速的找到我们需要的数据,大概就像下面这个图,索引就像是右边的二叉树,每个节点指向具体的数据的物理地址,先通过二叉树找到数据的位置,然后再去物理磁盘中获取数据. 但是不同的二叉树的特性不同,我们还要选择合适的树来作为索引,所

  • MySQL数据优化-多层索引

    MySQL数据优化-多层索引

    目录 一.多层索引 1.创建 2.设置索引的名称 3.from_arrays( )-from_tuples() 4.笛卡儿积方式 二.多层索引操作 1.Series 2.DataFrame 3.交换索引 4.索引排序 5.索引堆叠 6.取消堆叠 一.多层索引 1.创建 环境:Jupyter import numpy as np import pandas as pd a=pd.DataFrame(np.random.random(size=(4,4)),index=[['上半年','上半年','

  • MySQL数据库之索引详解

    MySQL数据库之索引详解

    目录 一.MySQL索引简介 二.MySQL五种类型索引详解 (一)普通索引 (二)唯一性索引 (三)主键索引 (四)复合索引 (五)全文索引 三.MySQL索引使用原则 总结 今天继续给大家介绍MySQL相关知识,本文主要内容是MySQL索引相关内容. 一.MySQL索引简介 索引是MySQL数据库为了加快数据查询的速度,给表中的某一个或者是某几个列添加的一种"目录".MySQL的索引是一个特殊的文件,但是InnoDB类型引擎(关于MySQL的引擎我们会在今后的文章中进行讲解)的表的

  • mysql数据库索引损坏及修复经验分享

    mysql表索引被破坏的问题及解决 下午上班,惊闻我的dedecms的网站出问题了,访问一看,果然全屏报错,检查mysql日志,错误信息为: Table '.\dedecmsv4\dede_archives' is marked as crashed and should be repaired 提示说cms的文章表dede_archives被标记有问题,需要修复.于是赶快恢复历史数据,上网查找原因.最终将问题解决.解决方法如下: 找到mysql的安装目录的bin/myisamchk工具,在命令

  • MySQL Hash索引和B-Tree索引的区别

    MySQL Hash索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引. 可 能很多人又有疑问了,既然 Hash 索引的效率要比 B-Tree 高很多,为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢?任何事物都是有两面性的,Hash 索引也一样,虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊

  • 简单介绍下MYSQL的索引类型

    一.介绍一下索引的类型 Mysql常见索引有:主键索引.唯一索引.普通索引.全文索引.组合索引 PRIMARY KEY(主键索引) ALTER TABLE `table_name` ADD PRIMARY KEY ( `column` ) UNIQUE(唯一索引) ALTER TABLE `table_name` ADD UNIQUE (`column`) INDEX(普通索引)      ALTER TABLE `table_name` ADD INDEX index_name ( `colu

  • Mysql使用索引实现查询优化

    索引的目的在于提高查询效率,可以类比字典,如果要查"mysql"这个单词,我们肯定需要定位到m字母,然后从下往下找到y字母,再找到剩下的sql.如果没有索引,那么你可能需要把所有单词看一遍才能找到你想要的. 1.索引的优点 假设你拥有三个未索引的表t1.t2和t3,每个表都分别包含数据列i1.i2和i3,并且每个表都包含了1000条数据行,其序号从1到1000.查找某些值匹配的数据行组合的查询可能如下所示: SELECT t1.i1, t2.i2, t3.i3 FROM t1, t2,

  • MySQL联合索引用法示例

    MySQL联合索引用法示例

    本文实例讲述了MySQL联合索引.分享给大家供大家参考,具体如下: 员工表 userid 部门表 deptid 员工部门表 条件:一个员工可以对应多个部门 问题:怎么样设置数据库,让其不能重复添加 userid 和deptid? uuid userid deptid 111 212 311(这个就不能让其添加) DROP TABLE IF EXISTS `dept`; CREATE TABLE `dept` ( `id` int(11) NOT NULL AUTO_INCREMENT, `dep

  • MySQL联合索引功能与用法实例分析

    MySQL联合索引功能与用法实例分析

    本文实例讲述了MySQL联合索引功能与用法.分享给大家供大家参考,具体如下: 联合索引又叫复合索引.对于复合索引:Mysql从左到右的使用索引中的字段,一个查询可以只使用索引中的一部份,但只能是最左侧部分.例如索引是key index (a,b,c). 可以支持a | a,b| a,b,c 3种组合进行查找,但不支持 b,c进行查找 .当最左侧字段是常量引用时,索引就十分有效. 两个或更多个列上的索引被称作复合索引. 利用索引中的附加列,您可以缩小搜索的范围,但使用一个具有两列的索引 不同于使用

  • 浅谈mysql的索引设计原则以及常见索引的区别

    索引定义:是一个单独的,存储在磁盘上的数据库结构,其包含着对数据表里所有记录的引用指针. 数据库索引的设计原则: 为了使索引的使用效率更高,在创建索引时,必须考虑在哪些字段上创建索引和创建什么类型的索引. 那么索引设计原则又是怎样的? 1．选择唯一性索引 唯一性索引的值是唯一的,可以更快速的通过该索引来确定某条记录. 例如,学生表中学号是具有唯一性的字段.为该字段建立唯一性索引可以很快的确定某个学生的信息. 如果使用姓名的话,可能存在同名现象,从而降低查询速度. 2．为经常需要排序.分组和联合操

  • MySQL中索引优化distinct语句及distinct的多字段操作

    MySQL通常使用GROUPBY(本质上是排序动作)完成DISTINCT操作,如果DISTINCT操作和ORDERBY操作组合使用,通常会用到临时表.这样会影响性能. 在一些情况下,MySQL可以使用索引优化DISTINCT操作,但需要活学活用.本文涉及一个不能利用索引完成DISTINCT操作的实例. 实例1 使用索引优化DISTINCT操作 create table m11 (a int, b int, c int, d int, primary key(a)) engine=INNODB;

  • MySQL中索引与视图的用法与区别详解

    前言 本文主要给大家介绍了关于MySQL中索引与视图的使用与区别的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. 索引 一.概述 所有的Mysql列类型都可以被索引. mysql支持BTREE索引.HASH索引.前缀索引.全文本索引(FULLTEXT)[只有MyISAM引擎支持,且仅限于char,varchar,text列].空间列索引[只有MyISAM引擎支持,且索引的字段必须非空],但不支持函数索引. MyISAM和InnoDB存储引擎的表默认创建BTREE索引,

  • MySQL组合索引与最左匹配原则详解

    前言 之前在网上看到过很多关于mysql联合索引最左前缀匹配的文章,自以为就了解了其原理,最近面试时和面试官交流,发现遗漏了些东西,这里自己整理一下这方面的内容. 什么时候创建组合索引? 当我们的where查询存在多个条件查询的时候,我们需要对查询的列创建组合索引 为什么不对没一列创建索引 减少开销 覆盖索引 效率高 减少开销:假如对col1.col2.col3创建组合索引,相当于创建了(col1).(col1,col2).(col1,col2,col3)3个索引 覆盖索引:假如查询SELECT

随机推荐