MySQL|索引背后

01

索引

以MySQL中的索引为例子总结。

数据库查询是数据库的最主要功能之一,实现高效的查询速度一定是MySQL非常关心的事情。

索引(Index)正是帮助MySQL高效获取数据的数据结构。

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构,因此先看下这两种树的基本概念,至于B-Tree/B+Tree涉及的主要操作比如,裂变等,大家可以进一步参阅其他书籍或博客学习。

02

B-树

m阶B-树也称作(ceil(m), m)树,如(2,3)树,称为3阶B树,(2,4)树称为4阶B树。

如下为4阶B-树,每个节点至少含有2个分支,至多含有4个分支,也就是说,每个节点至少含有1个数据节点,至多含有3个数据节点。

03

B+树

B+树和m阶的B-树的差异在于:

  1. 内节点(非叶子节点),只用来索引;
  2. 所有的外节点(叶子结点) 中包含了: 1) 全部关键字的信息 2) 指向含这些关键字记录的指针 3) 外节点(叶子结点) 本身依关键字的大小自小而大顺序链接。

如下所示,所有节点都有key域;叶节点的数据域上才真正存储着数据,而非叶节点的数据域只保存多个指针。

04

为什么是B+树?而不是红黑树

为什么MySQL选择了B+树,而不是红黑树作为数据库的索引呢?

B+Tree中一次检索最多需要h-1次I/O(根节点常驻内存),树的高度为O(logdN)。一般实际应用中,一个节点的分支数(出度d)是非常大的数字(通常大于100),因此树的高度会非常小(通常不超过3)。索引设计为B+数据结构,一次检索所需要的I/O次数就会很小。我们又知道,访问内存的延迟大约为ns级,而访问磁盘的延迟为ms级,这相当于,访问内存延迟如果1天的话,访问外存延迟需要2000年。

根据磁盘预读原理,B+树将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里。

而红黑树这种结构,h明显要深的多。并且,红黑树中逻辑上很近的节点(父子)物理上可能很远,无法利用局部性。

综上,B+树更适合做索引。

05

MyISAM和InnoDB存储引擎

在MySQL中,不同存储引擎对索引的实现方式是不同的,总结下MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。

第一列作为主索引的MyISAM引擎存储结构,要求主索引取值唯一。

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM不同。InnoDB的叶子节点的数据域保存了完整的数据记录,索引的key是数据表的主键

06

InnoDB的主键选择与插入优化

在使用InnoDB存储引擎时,建议使用一个与业务无关的自增字段作为主键。

InnoDB将数据记录本身存于主索引(一颗B+Tree)的叶子节点上。每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

这样就会形成一个紧凑的索引结构,近似顺序填满。

如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置:

此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

因此,只要可以,请尽量在InnoDB上采用自增字段做主键。

知道了这些基本知识,如何加以运用呢?see you!

本文部分参考了关于介绍索引的文章:

http://blog.codinglabs.org/articles/theory-of-mysql-index.html

以上,如果疏漏错误,请指正。

希望时间的流逝不仅仅丰富了我们的阅历,更重要的是通过提炼让我们得以升华,走向卓越。

本文分享自微信公众号 - 算法channel(alg-channel)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-03-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏沃趣科技

Oracle SCN HeadRoom分析与处理

最近几家客户的Oracle数据库开始集中爆发SCN HeadRoom问题,虽然SCN不会真正用完,但是数据库触碰到headroom天花板,还是可能有意想不到的情...

675100
来自专栏沃趣科技

semi-sync原主库加入集群阻塞问题分析

前段时间支持客户处理问题的时候,发现一个semi-sync复制主从切换原master加入集群时,复制同步阻塞,无法继续同步数据的问题,非常有参考意义,整理一下,...

509100
来自专栏张戈的专栏

gh-ost:在线DDL修改MySQL表结构工具

在之前,我分享过一次 pt-online-schema-change 在线 DDL 的工具实践记录,在实际使用过程中,发现部门的很多老系统大量使用了触发器,从而...

1.4K70
来自专栏沃趣科技

备份重于一切:远离“Gitlab删库事件”,QBackup是你的最佳选择!

作者简介:孙朝阳 沃趣科技高级产品经理。 案发现场: Gitlab删库事件回顾 Gitlab是大家很熟悉的开源Git代码托管工具,国内公司大多使用社区版自行搭...

41480
来自专栏沃趣科技

MySQL排序内部原理探秘

一、我们要解决什么问题 二、排序,排序,排序 三、索引优化排序 四、排序模式 4.1实际trace结果 4.2排序模式概览 4.2.1回表排序模式 4.2.2不...

61960
来自专栏沃趣科技

ASM磁盘容量改变的故障处理

某个数据库环境中的ASM磁盘,由于历史原因,全部配置为没有RAID信息的JBOD模式。今天在做产品升级,由于软件需要,需要将原来加入到ASM中每个JBOD的磁盘...

376140
来自专栏沃趣科技

QMonitor - PostgreSQL数据库监控正式发布!为PostgreSQL数据库运维人员而生

.

36380
来自专栏新智元

微软视觉智能技术突破: 首次 bot 生成视频标题,将开源大型数据库

【新智元导读】台湾国立清华大学与微软合作,首次实现了让机器自动生成视频标题。他们创建了一个系统,可以由机器人观看视频、找出视频中的亮点,然后生成简洁、吸引眼球的...

586130
来自专栏Java技术分享

SpringBoot第3小节:数据库操作(上)

Spring-Data-Jpa,定义了一系列对象持久化的标准,就是Hibernate的整合。这节讲的是datasouce和jpa的配置。 1.在pom.xml文...

32050
来自专栏张戈的专栏

MySQL在线DDL修改表结构的简单经验分享

摘 要 在线DDL修改生产环境的大表一直是运维、DBA一个很头痛的问题,本文分享一些相关经验,希望对还在头痛的同学能有所帮助,当然更希望路过的大神,如果有更靠...

47570

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励