MySQL索引实现原理分析

目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种B+Tree(B+树)作为索引结构。B+Tree是数据库系统实现索引的首选数据结构。在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。MyISAM索引实现MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的…

大家好,又见面了,我是你们的朋友全栈君。

       目前大部分数据库系统及文件系统都采用B-Tree(B树)或其变种B+Tree(B+树)作为索引结构。B+Tree是数据库系统实现索引的首选数据结构。在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。MyISAM索引实现MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:image.png这里设表一共有三列,假设我  

        在 MySQL 中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论 MyISAM 和 InnoDB 两个存储引擎的索引实现方式。

MyISAM 索引实现 

MyISAM 引擎使用 B+Tree 作为索引结构,叶节点的 data 域存放的是数据记录的地址。下图是 MyISAM 索引的原理图:
MySQL索引实现原理分析

这里设表一共有三列,假设我们以 Col1 为主键,则图 8 是一个 MyISAM 表的主索引(Primary key)示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。

辅助索引 

在 MyISAM 中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求 key 是唯一的,而辅助索引的 key 可以重复。如果我们在 Col2 上建立一个辅助索引,则此索引的结构如下图所示

MySQL索引实现原理分析

同样也是一颗 B+Tree,data 域保存数据记录的地址。因此,MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引,如果指定的 Key 存在,则取出其data 域的值,然后以 data 域的值为地址,读取相应数据记录。

MyISAM 的索引方式也叫做“非聚集索引”,之所以这么称呼是为了与 InnoDB的聚集索引区分。

InnoDB 索引实现 

虽然 InnoDB 也使用 B+Tree 作为索引结构,但具体实现方式却与 MyISAM 截然不同。

1.第一个重大区别是 InnoDB 的数据文件本身就是索引文件。从上文知道,MyISAM 索引文件和数据文件是分离的,索引文件仅保存数据记录的地址

而在InnoDB 中,表数据文件本身就是按 B+Tree 组织的一个索引结构,这棵树的叶点data 域保存了完整的数据记录。这个索引的 key 是数据表的主键,因此 InnoDB 表数据文件本身就是主索引。

MySQL索引实现原理分析

上图是 InnoDB 主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为 InnoDB 的数据文件本身要按主键聚集,

 1 .InnoDB 要求表必须有主键(MyISAM 可以没有),如果没有显式指定,则 MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL 自动为 InnoDB 表生成一个隐含字段作为主键,类型为长整形。

 同时,请尽量在 InnoDB 上采用自增字段做表的主键。因为 InnoDB 数据文件本身是一棵B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持 B+Tree 的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

MySQL索引实现原理分析

这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

 2.第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说,InnoDB 的所有辅助索引都引用主键作为 data 域。
例如,图 11 为定义在 Col3 上的一个辅助索引:

MySQL索引实现原理分析
 

聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引(回表):首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

 引申:为什么不建议使用过长的字段作为主键?

 因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。

聚簇索引与非聚簇索引 

InnoDB 使用的是聚簇索引, 将主键组织到一棵 B+树中, 而行数据就储存在叶子节点上, 若使用”where id = 14″这样的条件查找主键, 则按照 B+树的检索算法即可查找到对应的叶节点, 之后获得行数据。 若对 Name 列进行条件搜索, 则需要两个步骤:
第一步在辅助索引 B+树中检索 Name, 到达其叶子节点获取对应的主键。
第二步使用主键在主索引 B+树种再执行一次 B+树检索操作, 最终到达叶子节点即可获取整行数据。

MyISM 使用的是非聚簇索引, 非聚簇索引的两棵 B+树看上去没什么不同, 节点
的结构完全一致只是存储的内容不同而已, 主键索引 B+树的节点存储了主键, 辅助键索引B+树存储了辅助键。 表数据存储在独立的地方, 这两颗 B+树的叶子节点都使用一个地址指向真正的表数据, 对于表数据来说, 这两个键没有任何差别。 由于索引树是独立的, 通过辅助键检索无需访问主键的索引树。

为了更形象说明这两种索引的区别, 我们假想一个表如下图存储了 4 行数据。 其中Id 作为主索引, Name 作为辅助索引。 图示清晰的显示了聚簇索引和非聚簇索引的差异

MySQL索引实现原理分析

 

联合索引及最左原则

联合索引存储数据结构图:

MySQL索引实现原理分析

最左原则:

例如联合索引有三个索引字段(A,B,C)

查询条件:

(A,,)—会使用索引

(A,B,)—会使用索引

(A,B,C)—会使用索引

(,B,C)—不会使用索引

(,,C)—不会使用索引

 

*最后来一个问题:mysql假设一行数据大小为1k,则一颗层高为3的b+树可以存放多少条数据?

mysql页默认大小16k,如果数据行大小1k,叶子节点存放的完整数据,则叶子节点一页可以放16条数据;非叶子节点页面存放的是主键和指针,所以主要看主键是啥类型,假设是integer,则长度8字节,指针大小在innodb是6字节,一共14字节,所以非叶子节点每页可以存16384/14=1170个主键数据(1170个分叉),则三层b+树数据可以存1170*1170*16=21902400条数据。(千万级别)

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126446.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • proteus仿真之DS1302+LCD1602显示试验[通俗易懂]

    proteus仿真:DS1302LCD1602显示试验

  • JavaScript Array splice() 方法

    JavaScript Array splice() 方法语法array.splice(index,howmany,item1,…..,itemX)实例在位置2,添加新项目,并删除1个项目:varfruits=[“Banana”,”Orange”,”Apple”,”Mango”];fruits.splice(2,1,”Lemon”,”Kiwi”);在位置2,添加新项目varfruits=[“Banana”,”Orange”,”Apple”,”Mango”];fruits.s.

  • jQuery数据类型总结建议收藏

    jQuery除了包含原生JS中的内置数据类型(built-indatatype),还包括一些扩展的数据类型(virtualtypes),如Selectors、Events等。1.StringS

    2021年12月21日
  • centos7安装wget命令_centos中wget

    centos7安装wget命令_centos中wget方法一:yuminstallwget方法二:由于安装的centos是mini版,并且自带的软件源里也没有wget命令,只好自己下载了。网易源下载wget的连接下载后上传到centos上,CD到安装包的目录里,使用rpm安装。rpm-ivhwget-1.14-18.el7_6.1.x86_64.rpm安装包上传到服务器上可以用三种方法上传。centos安装…

    2022年10月10日
  • Gmail POP3设置

    Gmail POP3设置

    2021年11月15日
  • 阿里云ssl证书过期_阿里云acp证书含金量

    阿里云ssl证书过期_阿里云acp证书含金量阿里云提示内容如下:【阿里云】尊敬的:您域名com使用的SSL证书cert-还有1天过期,过期时间2021-04-21。为防止业务受影响,请提前5个工作日续费并更新证书。请尽快登陆控制台处。这是阿里云的SSL证书产品的到期通知,SSL证书主要用于HTTPS加密协议场景包括,电子商务、微信小程序、微信公众号、APP、公司网站等。SSL证书到期后会让对应的项目立即暂停服务,比如微信小程序就会立即停止服务,用户不能正常使用小程序,其它的场景也一样,所以SSL证书到期之前必须要尽快办理续费!SSL证

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号