MySQL与InnoDB(下)-B+树与索引

本节主要讲对记录的查找。关于数据库查询,首先要从查询算法的角度优化,从顺序查找、二分查找再到二叉树查找。但每一种算法只能用于特定的数据结构上,比如二分查找必须有序,二叉树查找只能用于二叉查找树上。数据库系统就有着一个使命,它维护着一种特殊的能够满足某种高级查找算法的数据结构,这个数据结构以某种方式指向具体的数据。而我们把这个数据结构就叫做索引。

上一篇讲到存储引擎负责数据的存储和提取。MySQL支持多种存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。

本节主要以InnoDB存储引擎为例来说明。InnoDB 存储引擎在绝大多数情况下使用 B+ 树建立索引,这是关系型数据库中查找最为常用和有效的索引,下面就讲一下为什么B+树索引常用且高效。

说道B+树,就要讨论B树与B+树的异同,而这属于数据结构的范畴,不在本文讨论范围之内。在这里大概讲两句,B树和B+树都属于B类树,为了使用B类树更快找到信息,原则就是在尽量多的在节点上存储相关信息,保证层数尽量少。B类树属于平衡树,每个节点到叶子节点的高度都相同。(更多内容去复习《数据结构》呗)

重点是B+树与B树的不同之处。B树的分支节点与叶子节点都存储数据,而B+树的分支节点存储的是索引,只有叶子节点存储具体的数据。所以对于B+树来讲,扫数据时只需要扫一遍叶子节点即可。下面通过B+树的两种索引方式:聚集索引和非聚集索引来详细说明。

聚集索引

聚集索引就是按照每张表的主键构造一颗B+树,同时叶子结点存放的即为整张表的行纪录数据。举个栗子,一个汉语字典,我们希望查找“张”,我们可以直接翻到字典的最后,找到zh开头,然后找到张。因为字典内容本身是按照拼音排版的,所以字典内容本身就是一个聚集索引。还是有些抽象,那么用下面实例来说明:

如上图,我们在名字字段上建立聚集索引.当需要根据此字段查找特定的记录时,数据库系统会根据特定的系统表查找此索引的根,然后根据指针查找下一个,直到找到。

例如我们要查询“Green”,由于它介于[Bennet,Karsen],据此我们找到了索引页1007,在该页中“Green”介于[Greane, Hunter]间,据此我们找到叶结点1133(也即数据结点),并最终在此页中找以了目标数据行。 此次查询的IO包括3个索引页的查询(其中最后一次实际上是在数据页中查询)。当然,如果是热点数据(访问频繁),还可能在缓存中查找到。

聚集索引能够让我们在索引的页节点上直接找到数据。此外,由于定义了逻辑顺序,聚集索引能够特别快的访问针对范围的查询。 。比如:如果我们指定一列xxx(或多列)聚集索引,则如果遇到这种语句select* from table where xxx>’2017’ and xxx

非聚集索引

聚集索引中存放着一条行记录的全部信息,而非聚集索引中只包含索引列和一个用于查找对应行记录的『书签』。也就是说,对于非聚集索引,表数据存储顺序与索引顺序无关,叶结点包含索引字段值及指向数据页数据行的逻辑指针。这里也举个栗子:在查找一个不认识的字的时候,我们可以先通过字典的偏旁部首目录,找到字在哪一页,然后通过页码找到“张”。因为字典不是根据偏旁部首排版的,所以需要通过两步才能真正找到。还是有些抽象?如下图:

可以看到,B+树的叶子节点存放的依然是索引,而且还存放着该索引代表的具体数据在那一页。与聚集索引相比:

叶子节点不是数据节点(所以数据不是聚集的)。

叶子节点为每个索引存储一个键-指针映射,可以直接通过该叶子节点找到具体的数据节点页。

我们通过上图发现,叶子节点还保存着一个指针偏移量,通过它可以找到具体的数据行。

其他分支索引节点也与上述存储类似,只不过指向的是下一级的索引节点。

两者的关系

由于实际的数据页只能按照一棵B+树来进行排序,因此每张表只能拥有一个聚集索引。而非聚集索引的存在并不影响数据在聚集索引的组织,因此每张表上可以有多个非聚集索引,非聚集索引页也因此被称作辅助索引。

参考资料

cnblogs:B树和B+树的总结:

http://www.cnblogs.com/George1994/p/7008732.html

浅入浅出MySQL和InnoDB:

https://draveness.me/mysql-innodb

CSDN;深入理解索引B+树存储:

CNBLOGS:InnoDB索引原理:

https://www.cnblogs.com/George1994/p/7324759.html

oschina:聚集索引与非聚集索引:

https://my.oschina.net/osenlin/blog/287558

CSDN:浅析聚集索引:

《MySQL技术内幕:InnoDB存储引擎》

第五章:索引与算法

本文来自企鹅号 - 搬砖的小学生媒体

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏JetpropelledSnake

SQL学习笔记之项目中常用的19条MySQL优化

MySQL对于IN做了相应的优化,即将IN中的常量全部存储在一个数组里面,而且这个数组是排好序的。但是如果数值较多,产生的消耗也是比较大的。再例如:select...

973
来自专栏java一日一条

InnoDB引擎算法和优化

索引是应用程序设计和开发的一个重要方面。如果索引太多,应用的性能可能会受到影响;如果索引太少,对查询性能又会产生影响。

671
来自专栏java达人

漫谈数据库索引

一、引言 对数据库索引的关注从未淡出我的们的讨论,那么数据库索引是什么样的?聚集索引与非聚集索引有什么不同?希望本文对各位同仁有一定的帮助。有不少存疑的地方,诚...

1769
来自专栏代码世界

MYSQL之索引原理与慢查询优化

一、索引 1、介绍   一般的应用系统,读写比例在10:1左右,而且插入操作和一般的更新操作很少出现性能问题,在生产环境中,我们遇到最多的也是最容易出现问题的,...

46313
来自专栏数据分析

[数据库基础]——索引

一、引言 对数据库索引的关注从未淡出我的们的讨论,那么数据库索引是什么样的?聚集索引与非聚集索引有什么不同?希望本文对各位同仁有一定的帮助。有不少存疑的地方,...

3247
来自专栏13blog.site

Spring+SpringMVC+MyBatis+easyUI整合优化篇(十二)数据层优化-explain关键字及慢sql优化

本文提要 从编码角度来优化数据层的话,我首先会去查一下项目中运行的sql语句,定位到瓶颈是否出现在这里,首先去优化sql语句,而慢sql就是其中的主要优化对象,...

34611
来自专栏jouypub

MySQL查询语句优化

在项目中经常和MySQL数据库打交道,写过各种各样的SQL,也遇到过各种问题,针对遇到的各种场景,记录一些解决方案,主要是MySQL索引问题。

110
来自专栏Linyb极客之路

MySql查询性能优化

在访问数据库时,应该只请求需要的行和列。请求多余的行和列会消耗MySql服务器的CPU和内存资源,并增加网络开销。 例如在处理分页时,应该使用LIMIT限制My...

1014
来自专栏抠抠空间

MySQL 之 索引原理与慢查询优化

浏览目录 一 索引介绍 二 索引方法 三 索引类型 四 聚合索引和辅助索引  五 测试索引 六 正确使用索引 七 组合索引 八 注意事项 九 查询计划 十 慢日...

3627
来自专栏恰同学骚年

《T-SQL查询》读书笔记Part 3.索引的基本知识

索引优化是查询优化中最重要的一部分,索引是一种用于排序和搜索的结构,在查找数据时索引可以减少对I/O的需要;当计划中的某些元素需要或是可以利用经过排序的数据时,...

953

扫码关注云+社区