当前位置: 首页>数据库>正文

数据库int索引 数据库中索引

什么是索引

索引是帮助数据库高效获取数据的数据结构。索引是在基于数据库表创建的,它包含一个表中某些列的值以及记录对应的地址,并且把这些值存储在一个数据结构中。索引是以索引文件的形式存放于磁盘中。实际上,索引也是一张表,该表保存了主键与索引字段,并指向实体表的记录。

索引的优缺点

在mysql优化中,当我们定位到了慢查询语句后,我们都会适当给它建立索引来提高查询效率。是的,索引的作用就是高效提高查询效率,这种效果是非常明显的。不过,建立索引后,也带来了一些弊端,那就是作增加、删除等更新操作时,效率会下降,因为要对这些索引文件进行维护,必然导致效率下降。

索引的数据结构

之所以加了索引后,查询效率就快了,这很大程度上取决索引背后所使用的数据结构。在查找算法中,二分查找比遍历一遍的效率高许多,而在数据结构中,二叉查找树,甚至其进化版的红黑树的查找效率也是很高的,尤其是红黑树,能保证在最坏情况下,基本的动态几何操作的时间均为O(logn)。对于红黑树还不是很理解的话,可以看博主之前总结过的这篇文章初入红黑树。

但是,多数数据库的索引却是使用了B树,而不是红黑树这种数据结构。在MySQL中则使用了B树的优化版B+树。这些都是有原因的。

首先第一个问题:为什么不使用红黑树,而是使用B树?

原因在于B树能够充分利用磁盘预读原理,而红黑树由于逻辑上很近的节点,物理上可能很远,无法利用局部性,导致效率比B树差很多。我们来了解一下什么是局部性原理和磁盘预读原理

局部性原理与磁盘预读:

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,
磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,
要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,
而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,
顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理: 
当一个数据被用到时,其附近的数据也通常会马上被使用。 
程序运行期间所需要的数据通常比较集中。 
由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

我们来分析一下B树的性能效率

假设B树的高度为h,B树一次检索最多需要h - 1次I/O(因为根节点常驻在内存中)。

h =   

数据库int索引 数据库中索引,数据库int索引 数据库中索引_存储引擎,第1张

但数据库系统巧妙利用了磁盘预读原理后,将一个节点的大小设为等于一个页。B树新建一个节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个节点只需一次I/O。

渐进复杂度变为O(h)= 

数据库int索引 数据库中索引,数据库int索引 数据库中索引_数据_02,第2张

,一般实际应用中,出度d是非常大的,通常超过100,因此h非常小(通常不超过3),三层的B树可以存放上百万数据。也就是说,最多需要2次I/O就可以查找目标数,性能可见极其强悍!

而红黑树由于逻辑上很近的节点,物理上可能很远,无法利用局部性,其渐进复杂度也为之前的O(h)。效率与B树无法比较。

第二个问题:mysql的索引为什么使用B+树而不是B树?

这里有一篇漫画,说的是B树与B+树的一些知识点,大家可以看一下

之所以要用B+树,原因在于B+树的特性。

1.B+树的中间节点只保存索引元素,不保存数据,导致可以有更多的空间存放更多的索引,减少I/O次数。

2.B+树中间节点可以存放的元素个数为K,而B树为K - 1(K 为该节点的子树数目),导致B+树显得更加“矮胖”,更符合做索引。

3.B+树叶子节点才存放索引文件,并且各区间叶子节点是以指针连起来,而B树是节点都可以存放索引和数据,这个优化将在范围查询时,让B+树显得很方便,只要顺着指针链,找下去就可以了,而B树要做范围查找,则要进行中序遍历,导致进行的I/O次数比B+树多。

聚簇索引与非聚簇索引

mysql中普遍使用B+Tree做索引,但在实现上又根据聚簇索引和非聚簇索引而不同。

聚簇索引

所谓聚簇索引,就是指主索引文件和数据文件为同一份文件,聚簇索引主要用在Innodb存储引擎中。在该索引实现方式中B+Tree的叶子节点上的data就是数据本身。

非聚簇索

非聚簇索引就是指B+Tree的叶子节点上的data,并不是数据本身,而是数据存放的地址。主索引和辅助索引没啥区别,只是主索引中的key一定得是唯一的。主要用在MyISAM存储引擎中

这里顺便总结一下mysql两种存储引擎特性和优缺点

MyISAM:

  1. 不支持事务,但是每次查询都是原子的;
  2. 支持表级锁,即每次操作是对整个表加锁;
  3. 存储表的总行数;
  4. 一个MYISAM表有三个文件:索引文件、表结构文件、数据文件;
  5. 采用菲聚集索引,索引文件的数据域存储指向数据文件的指针。辅索引与主索引基本一致,但是辅索引不用保证唯一性。

优点:查询数据相对较快,适合大量的select,可以全文索引,会保持表的具体行数

缺点:不支持事务,不支持外键,并发量较小,不适合大量update操作

InnoDb:

  1. 支持ACID的事务,支持事务的四种隔离级别;
  2. 支持行级锁及外键约束:因此可以支持写并发;
  3. 不存储总行数;
  4. 一个InnoDb引擎存储在一个文件空间(共享表空间,表大小不受操作系统控制,一个表可能分布在多个文件里),也有可能为多个(设置为独立表空,表大小受操作系统文件大小限制,一般为2G),受操作系统文件大小的限制;
  5. 主键索引采用聚集索引(索引的数据域存储数据文件本身),辅索引的数据域存储主键的值;因此从辅索引查找数据,需要先通过辅索引找到主键值,再访问辅索引;最好使用自增主键,防止插入数据时,为维持B+树结构,文件的大调整。

优点:支持事务,支持外键,并发量较大,适合大量更新操作

缺点:不适合大量的查询操作,查询数据相对较慢、不保存表的具体行数,需要扫描一遍表。


https://www.xamrdz.com/database/6mh1942052.html

相关文章: