索引是存储引擎用于快速找到数据记录的一种数据结构,就好比一本书的目录,可以通过目录找到对应文章的章节的页码,可以快速定位到需要的文章。Mysql中同理,进行数据查找时,首先查看查询条件是否命中某一条索引,符合则通过索引查找相关的数据,如果不符合就需要全表扫描,需要一条一条的查找记录,直到找到与条件相符合的记录。我们建立索引的目的是减少磁盘io的次数,加快查询速度;
Mysql官方对索引的定义为:索引是帮助Mysql高效获取数据的数据结构.
索引的本质:索引是数据结构,可以认为是排好序的快速查找的数据结构。这些数据结构以某种方式指向数据,这样就可以在这些数据结构的基础上实现高级查找算法
索引是在存储引擎中实现的,因此每种存储引擎的索引不一定完全相同,不一定支持所有的索引类型。存储引擎可定义每张表的最大索引树和最大索引长度。支持每个表至少16个索引,总索引长度至少为256字节。
在没有索引的情况下,我们在表中进行数据查找的时候,由于数据是存储在数据页中的,不论是根据主键还是其他列的值进行查找,由于我们不能快速的定位到记录所在的页,只能从第一页沿着双向链表一直往下找,在每一页中出查找,要遍历所有的数据页,这种方式超级耗时,尤其是在数据量特别大的时候(我们将磁盘中数据页加载到内存中也是十分的耗时的)。
该索引并不是一种单独的索引类型,而是一种数据存储方式(所有的用户记录都存储在了叶子节点上),也就是所有的索引即数据,数据即索引.
上边介绍的聚簇索引只能搜索条件是主键值时才能发挥作用,因为B+树中数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该怎么办?肯定不能是从头到尾沿着链表一次遍历记录一遍。
答案:我们可以多建几棵B+树,不同的B+树中的数据采用不同的排序规则。比方说我们用其他列的大小作为数据页,页中记录的排序规则,再建一棵B+树,效果如下图所示:
但是这个B+树的叶子节点中的记录只储存当前列和主键两个列,所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。
概念:回表
我们根据自定义列大小的列排序的B+树只能确定我们要查找记录的主键值,如果我们想根据自定义列查找到完整的用户记录的话,需要到聚簇索引中再查找一遍,这个过程称为回表。也就是根据自定义的列值查询一条完整的用户记录需要使用2棵B+树。
问题 为什么我们还需要一次回表操作呢?直接把完整的用户记录放到叶子节点不行吗?
回答 如果把完整的用户记录放到叶子节点是可以不用回表。但是太占用地方了,相当于每建立一颗B+树都需要把所有的用户记录再都拷贝一遍,浪费储存空间。
因为这种按照非主键列建立的B+树需要建立一次回表操作才可以定位到完整的用户记录,这种B+树称为二级索引(secondary index),或称为辅助索引。
非聚簇索引的存在不影响数据在聚簇索引中的组织,所以一张表可以有多个非聚簇索引。
小结: 聚簇索引与非聚簇索引的原理不同,使用上也有一些区别
- 聚簇索引的叶子节点存储的就是我们的数据记录,非聚簇索引的叶子节点存储的是数据位置。非聚簇索引不会影响数据表的物理存储顺序。
- 一个表只能有一个聚簇索引,因为只能有一种排序储存的方式,但是可以有多个非聚簇索引,也就是多个索引目录提供数据检索
- 使用聚簇索引的时候,数据查询效率高,但如果对数据进行插入、删除、更新等操作,效率会比非聚簇索引低
1. 跟页面位置万年不变
过程中特别注意的是:一个B+树索引的根节点自诞生之后起,就不会再移动。这样只要我们对某个表建立一个索引,那么它的根节点的页号便会被记录到某个地方,然后是InnoDB存储引擎需要用到这个索引的时候,都会从那个固定的地方取出页号,从而访问这个索引。
2. 内节点中目录项记录的唯一性
对于二级索引来说,如果我们的目录项只存储索引列+页号,这样存在问题,当用户新增记录的索引列值一样,主键以及其他列数据不一致时候,内节点数据不唯一,找不到自己所在的页,为了保证新插入的记录能找到自己在那个页中,我们需要保证B+树中同一层内节点的目录项记录除页号这个字段以外是唯一的。所以二级索引的内节点的目录项记录的内容实际上是由三个部分构成的索引列的值+主键值+页号,这样保证了B+树每一层节点中各条目录项记录除页号这个字段外是唯一的,简历的示意图如下:
3. 一个页面最少存储2条记录
一个B+树只需要很少的层级就可以轻松存储数亿条记录,查询速度相当不错!这是因为B+树本质上就是一个大的多层级目录,每经过一个目录时都会过滤掉许多无效的子目录,查到最后访问到存储真实数据的目录。那如果一个大的目录中只存放一个子目录是个啥效果呢?那就是目录层级非常非常非常多,而且最后的那个存放真实数据的目录中只能存放-条记录。费了半天劲只能存放一条真实的用户记录? 所以InnoDB的一个数据页至少可以存放
两条记录。
MyISAM引擎使用B+Tree作为索引结构,叶子节点的data域存放的是数据记录的地址。
B树的英文是Balance Tree,也就是多路平衡查找树。简写为B-Tree (注意横杠表示这两个单词连起来的意思,不是减号)。它的高度远小于平衡二叉树的高度。
B树作为多路平衡查找树,它的每一个节点最多可以包括M个子节点,“M 称为B树的阶|。每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了x个关键字那么指针数就是x+1.对于一个100阶的B树来说,如果有3层的话最多可以存储约100万的索引数据。对于大量的索引数据来说,采用B树的结构是非常适合的,因为树的高度要远小于二叉树的高度。
B+树中并不直接存储数据,这样有什么好处?
首先,B+ 树查询效率更稳定。因为B+树每次只有访问到叶子节点才能找到对应的数据,而在B树中,非叶子节点也会存储数据,这样就会造成查询效率不稳定的情况,有时候访问到了非叶子节点就可以找到关键字,而有时需要访问到叶子节点才能找到关键字。
其次,B+树的查询效率更高。这是因为通常B+树比B树更矮胖(阶数更大, 深度更低),查询所需要的磁盘I/O也会更少。同样的磁盘页大小,B+ 树可以存储更多的节点关键字。
不仅是对单个关键字的查询上,在查询范围上,B+ 树的效率也比B树高。这是因为所有关键字都出现在B+树的叶子节点中,叶子节点之间会有指针,数据又是递增的,这使得我们范围查找可以通过指针连接查找。而在B树中则需要通过中序遍历才能完成查询范围的查找,效率要低很多。
B+树的存储能力如何?为什么查找行记录,一般只要1到3次IO就行?
InnoDB存储引擎中页的大小为16KB,-般表的主键类型为INT (占用4个字节)或BIGINT (占用8个字节),指针类型也一般为4或8个字节,也就是说一个页(B+Tree 中的一个节点)中大概存储16KB/(8B+8B)=1K个键值(因为是估值,为方便计算,这里的K取值为10^3。也就是说一个深度为 3的B+Tree索引可以维护10^3* 10^3 * 10^3= 10亿条记录。(这里假定一 个数据页也存储10^3条行记录数据了)实际情况中每个节点可能不能填充满,因此在数据库中,B+Tree 的高度一般都在2~4层。MySQL 的InnoDB存储弓|擎在设计时是将根节点常驻内存的,也就是说查找某-键值的行记录时最多只需要1~3次磁盘I/0操作。
为什么说B+树比B树更适合在实际应用中操作系统的文件索引和数据库索引?
- B+树的磁盘读写代价更低B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I0读写次数也就降低了。
- B+树的查询效率更加稳定由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。
为了减少IO次数,索引树会一次性加载吗?
- 数据库索引是存储在磁盘上的,如果数据量很大,必然导致索引的大小也会很大,超过几个G。
- 当我们利用索引查询时候,是不可能将全部几个G的索引都加载进内存的,我们能做的只能是:逐-加载每一个磁盘页,因为磁盘页对应着索引树的节点。
二叉搜索树的每个节点存储的都是(K,V)结构,key是值(图上的Col2),value则是该key所在行的文件指针(地址:0x07);