本文整理自网络,侵删。
目录
- 1索引的概念
- 1.1定义
- 1.2类型
- 1.3作用
- 2索引的数据结构B+树的演进过程
- 2.1问题
- 2.2问题
- 2.3问题:怎么建目录呢?给每一个页都建一个目录吗?
- 2.4索引树、页的分裂与合并
- 2.5根据我们刚才推演的,延申出几个面试题
- 3什么是二级索引树
- 3.1那么二级索引树怎么排序?
- 3.2索引桥的概念是什么呢(最左匹配原则)?
- 3.3回表、覆盖索引、索引下推
- 3.4延申几个面试题:
- 3.5二级索引树的总结
- 4主键索引与二级索引的区别
1索引的概念
1.1定义
索引在关系型数据库中,是一种单独的、物理的对数据库表中的一列或者多列值进行排序的一种存储结构,它是某个表中一列或者若干列值的集合,还有指向表中物理标识这些值的数据页的逻辑指针清单。
索引的作用相当于图书的目录,可以根据目录重点页码快速找到所需要的内容,数据库使用索引以找到特定值,然后顺着指针找到包含该值的行,这样可以是对应于表的SQL语句执行得更快,可快速访问数据库表中的特定信息。
1.2类型
在InnoDB里面,索引类型有三种,普通索引、唯一索引(主键索引是特殊的非空的唯一索引)、全文索引。
普通(Normal):也叫非唯一索引,是普通索引,没有任何限制。唯一(Unique):唯一索引要求键值不能重复(可以为空),主键索引其实是一种特殊的唯一索引,不过他还多了一个限制条件,要求键值不能为空。主键索引用 primary key 创建。全文(Fulltext):针对比较大的数据,比如我们存放是文章,课文,邮件,等等,有可能一个字段就需要几kb,如果要解决like查询在全文匹配的时候效率低下的问题,可以创建全文索引。只有文本类型的字段才可以创建全文索引,比如char、varchar、text。MyISAM和InnoDB都支持全文索引。
1.3作用
一句话总结:
索引能够提高数据检索的效率,降低数据库的IO成本。
提出问题:我们用空间换时间,但是他的数据结构、查询的IO成本、以及是如何存储数据的呢?
2索引的数据结构B+树的演进过程
我们以一个 Page
的视角去看我们的B+树演进过程。
页是InnoDB管理存储空间的基本单位,InnoDB将数据库中的数据都是存储在页这个基本存储单位?的;页也是内存和磁盘交互的基本单位,数据库从磁盘中读取若?个页??的数据到内存,也将内存中若?个页??的数据刷新到磁盘中。
?个页的内存??为16KB。
假设我们要执行这个SQL,得到了10条记录:
SELECT * FROM INNODB_USER LIMIT 0 , 10;
假如一条记录的数据大小是4K,那么我们一个Page页能存多少条数据呢?
16K 除以 4K 得到 4条记录,对吧。
Page里面的每一条数据都有一个关键的属性叫做record_type
0 普通用户记录 1 目录的索引记录 2 最小 3 最大
画个图示例一下页里面数据是怎么放的:
这个是我们的Page页,每个Page页都会存放数据,按照主键有序存放数据
我们知道数据的存储是顺序IO的,方便存放,可是存放方便那查询是不是就不方便了,如果查的是最后一个是不是要遍历整个页的数据?
2.1问题
假如我们要查一条数据要怎么查?怎么才能快速查到数据?
- 如果我们Page页中的数据是有连接方式的,想想我们学过的数据结构,哪种结构查询快?
- 如果我们Page页中的数据是有连接方式的,就能够解决啊!没错,就是链表
Page页中的数据是怎么连接的(数据在同一个页中):
MySQL把页中的数据通过单向链表连接起来,如果是根据主键去查询,使用二分法定位会非常快,如果是根据非主键索引去查,只能从最小的一个个开始遍历单向链表。
多个Page页是怎么建立连接(数据在不同的页中):
MySQL把不同的页通过双向向链表建立链接,这样我们就可以通过上一页找到下一页,通过下一页找到一页,由于我们现在不能快速定位到数据的所在页,我们只能从第一个页沿着双向链表一直往下找,在每个页中再按照在同一页的方式去查找指定的记录,这个也是全表扫描嘛。
2.2问题
当Page页越来越多,查询会出现什么问题、怎么解决怎么优化?
当我们链表记录变多,由于不能直接定位,我们出现了查询缓慢问题,深入思考,所谓的查询缓慢,其实就是下面两个问题:
- 查询时间的复杂度0(N)
- 读写磁盘的IO次数过多
我们想一下,平时看书时,想找某一页的资料,怎么做的?
查目录对不对?目录是个啥?不就是索引嘛!
百度上随便找个目录,贴个图:
我们发现,这个目录里面有两个很重要的信息:
- 内容简介(章节标题)
- 所在的页码
我们这个我们参考一个图书的目录的思想来达到我们快速查询数据的目的:
给数据加一个目录,查数据,我们先根据目录页找到数据在哪个页的哪个地方,提升查询性能。
可是,
2.3问题:怎么建目录呢?给每一个页都建一个目录吗?
建目录是不是要有规律?比如字典的目录就是根据字母顺序建立的,你想到了什么?没错就是主键,Mysql里自增的主键刚好符合我们的要求,有规律,内容还少,而且不可重复,真是完美的目录,我们将每一页的主键按规律存储一下,添加一个指针指向数据的位置,查询时直接根据主键大小,用二分法快速找到目录,然后找到数据。
但是我们要给每一个数据页都建目录吗?好像还必须如此,不给每一个页建数据,你怎么定位到页里的数据?难道全页扫描吗?
但是给每一个页都建目录,随着目录页也出现多个,我们一个个目录也去遍历查询性能也会下降。
我们可不可以给目录建一个目录?
于是,我们可以通过为目录页也建立一次目录,向上抽取一层根结点,这样就更加便于我们进行查询了。
这棵树,因为是根据主键存储的,所以我们把它称之为主键索引树,因为主键索引树里存储了我们的表里的所有数据,那么在MySQL中 索引即数据,数据即索引也是这个原因了。
这就是MysqlB+树主键索引树的数据结构,怎么样,是不是比你直接死记硬背得到的知识印象更深刻
2.4索引树、页的分裂与合并
我们找到了提升查询性能的办法,那么,当Page页出现增加、修改、删除,都会遇到什么问题?
相关阅读 >>
oracle使用sql语句增加字段示例(sql删除字段语句)
sql server 2008中的代码安全(八)透明加密(tde)
更多相关阅读请进入《sql》频道 >>
数据库系统概念 第6版
机械工业出版社
本书主要讲述了数据模型、基于对象的数据库和XML、数据存储和查询、事务管理、体系结构等方面的内容。
转载请注明出处:木庄网络博客 » MySQL索引详解及演进过程及面试题延伸
相关推荐
评论
管理员已关闭评论功能...