MySQL官方对索引的定义为:索引(Index)是帮助MySQL 高效 获取数据的数据结构,而MYSQL使用的数据结构是:B+树
在这里推荐大家看一本书,《深入理解计算机系统的书》
程序和数据的访问都有聚集成群的倾向,在一个时间段内,仅使用其中一小部分,在最近的将来将用到的信息很可能与现在正在使用的信息在空间地址上是临近的(称空间局部性),或者最近访问过的程序代码和数据,很快又被访问的可能性很大(称时间局部性)。
预读的长度一般为页(page)的整数倍 页是存储器的逻辑块,操作系统往往将主存和磁盘存储区分割成连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页大小通常为4K),主存和磁盘以页为单位交换数据
在使用数据库中,通常数据库查询是数据库的最主要功能之一。但每种查找算法都只能应用于特定的数据结构之上。
索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。
id | name |
---|---|
1 | 手机 |
2 | 电脑 |
3 | 平板 |
这里有一个mysql数据文件,有Id和name两个列,如果我们用hash格式存储的话(hash表),我们只要计算出某一个列的hash值,把它按照按照数组的长度取一个模,就可以取到从0-7n个下标的位置,这样的话效率其实是比较高的,但是用hash表存储,它具备一定的缺点 :
索引格式:
对于树有他是有一个更新跌过的顺序在里面,不要一上来就看结构,先是了解什么树,树都是由一个树根,然后有n多个分支组成,这些分支就是一些树形结构,多你有多个树分支(多元素)的时候,这个时候查找效率就会比较低,因此就有了二叉树的东西,二叉树为什么会好用一点,因为二叉树它是都有两个分支,但是两个分支的话,会导致一个效果,就是每次我们在查找数据的时候,类似于二分查找的,但是二叉树也有自己不太好的地方,大家可以看我们上图中的二叉树的索引格式,在左边的节点会比较短一点(只需要读三次),而右边的节点会长很多(需要读五次),会导致树的深度比较深,每一次树的节点读取,都会有一次IO,深度越高,IO越高,会影响我们数据读取的效率,因此也有了(平衡二叉树)和(红黑树)
平衡二叉树: 维护一个平衡,就是左子树和右子树高度之差,不能大于1,但是对于我们上面的格式就不太适合,因为他已经超过1了,但是AVL树也会有一个问题就是调整的次数太频繁了,它里面涉及到了一个操作就是旋转,一种左旋,一个右旋,为了保持平衡需要N多次的旋转,这样的旋转其实是很浪费时间的,每次新增或者删除的时候,都要经历N多次旋转,效率太低了
推荐大家一个网站,可以直接看到AVL树操作过程,有不了解的同学可以去看一看,很形象:AVL Trees (Balanced binary search trees)
红黑树: 本身也是一个平衡树,但是它从中间做了一个权衡,就是损失一部分平衡的性能,但是又保持了相对的平衡,它做了这样一个操作,就是最长子树的高度,只要不超过最短子树的两倍,就可以了,同时在红黑树中它引入了红和黑两个节点信息,有了这些信息它可以帮助我们做一个平衡,在AVL树有旋转保持平衡,而红黑树有了旋转和变色两种来保持平衡,红黑树是AVL树的进阶,它损失了一部分平衡的性能,但是维护了我们插入和删除数据的高效,虽然它损失了一部分性能,但是它依然是一个平衡树,既然是平衡树,他最长子树,不超过最短子树的两倍,那意味着如果最短子树是 4 ,那么最长子树就是8,这样在们查找数据的时候,又不是一个二分查找了,效率又会变低
无论是二叉树还是红黑树,都会因为树的深度过深而造成IO次数变多,影响数据的读取的效率,最重要的就是减少IO
IO是我们IT行业中的一个瓶颈,一个是磁盘IO一个是网络IO,我们作为软件开发,是没有办法去调整硬件方面的瓶颈,只能从从程序里面减少我们的IO量,我们有两个方向,一个是减少IO的次数,一个是减少IO的量,从这两个方面去解决,比如说原来我们读取数据要读10次,现在只要读取一次,这样的IO量就少了10倍,原来我们需要读1MB的数据,现在只要读1KB的数据, 这也就是为什么我们在写mysql查询语句的时候不推荐使用select * from ,因为这样的查询会查询到N多个字段,本来我只要两个字段,但是给了我30个字段,这样会导致IO量增加了,因此我们就会去考虑,关于索引的次数能不能减少,因此下面就引出了我们的——B树
B树的特点:
B树结构说明:
示例图说明: 每个节点占用一个磁盘块,一个节点上有两个升序排序的关键字和三个指向子树根节点的指针,指针存储的是子节点所在磁盘块的地址,两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为列,关键字为16和34,p1指针指向的子树的数据范围小于16,P2指针指向的子树的数据范围为16-34,P3指针指向的子树的数据范围大于34 查找关键字(28)过程:
缺点:
B+Tree 是在BTree 的基础之上做的一种优化,变化如下:
如果当前磁盘块下没有其他节点,就是 叶子节点,反之就是 非叶子节点
结构图:
注意:在B+Tree上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有的叶子节点(即数据节点)之间是一种链式环结构,因此可以对B+Tree进行两种查询运算,一种是对于主键的范围查找和分页查找,另一种是从根节点开始,进行随机查找。
id | name |
---|---|
1 | 电脑 |
2 | 手机 |
3 | 冰箱 |
4 | 空调 |
5 | 风扇 |
6 | 彩电 |
存放的是对应的行记录
1、InnoDB是通过B+Tree结构对主键创建索引,然后叶子节点中存储记录,如果没有主键,那么会选择唯一键,如果没有唯一键,那么会生成一个6位的row_id来作为主键 2、如果创建索引的键是其他字段,那么在叶子节点中存储的是该记录的主键,然后在通过主键索引找到对应的记录
在name上建立索引
在name列上存放的是ID,然后通过ID去找到对应的key和数据
下面0X0022其实就是地址,显示根据我们的ID,找到我们的地址,然后通过地址去找到对应的表对应的数据
mysql索引的五种类型:主键索引、唯一索引、普通索引和全文索引、组合索引。通过给字段添加索引可以提高数据的读取速度,提高项目的并发能力和抗压能力
1 | MyISAM | InnoDB |
---|---|---|
索引类型 | 非聚簇索引 | 聚簇索引 |
支持事务 | 否 | 是 |
支持表锁 | 是 | 是 |
支持行锁 | 否 | 是 |
支持外键 | 否 | 是 |
支持 全文索引 | 是 | 是(5.6后支持) |
使用操作类型 | 大量select | 大量insert、delete、update |
写这篇文章的时候,小农的公司群消息不断,因为项目中有问题需要我去解决,今天的mysql索引机制就到这里了,对于本文中有不懂或者疑问的地方,欢迎同学们在下面留言,小农看见了会第一时间回复大家,谢谢,大家加油~