MYSQL的索引(一)

发布时间:2024年01月15日

本章概览

概览
索引的出现就是为了提高数据查询的效率,实际上可以提高读写效率的数据节后有很多

索引常见模型

哈希表是一种以键 - 值(key-value)存储数据的结构,用哈希函数把key计算成一个值,这个值代表一个位置,可能会出现不同key计算出位置相同,这是再拉出一个链表。这种结构等值查询和插入的效率都很快,但是不是按顺序插入的,使用区间查询的时候就需要全部扫描一遍了。
所以,哈希表这种结构适用于只有等值查询的场景,比如 Memcached 及其他一些 NoSQL 引擎。

有序数组在等值查询和范围查询场景中性能都很优秀,时间复杂度在O(log(N)),但是更新数据的时候需要数据搬移,所以,有序数组索引只适用于静态存储引擎,比如你要保存的是 2017 年某个城市的所有人口信息,这类不会再修改的数据。

二叉搜索树的特点是:父节点左子树所有结点的值小于父节点的值,右子树所有结点的值大于父节点的值,这个时间复杂度是 O(log(N))。
数可以有二叉也可有多叉,二叉树的查询效率最高,实际上数据库存储不用二叉树,原因在于索引不仅存在内存也在磁盘上,寻址需要时间,层数高意味着磁盘数据块多,查询随机读取数据块耗时多。

以 InnoDB 的一个整数字段索引为例,这个 N 差不多是 1200。这棵树高是 4 的时候,就可以存 1200 的 3 次方个值,这已经 17 亿了。考虑到树根的数据块总是在内存中的,一个 10 亿行的表上一个整数字段的索引,查找一个值最多只需要访问 3 次磁盘。其实,树的第二层也有很大概率在内存中,那么访问磁盘的平均次数就更少了。

innodb最小存储单元是数据页16k,整型bigint大小是8byte, 指向子树的pointer是6byte,1600/14约等于1170。

这样可以减少随机访问读取数据块

Innodb的索引模型

  1. 在innodb位存储引擎的mysql中,每张表就是多个B+树,每一个索引在 InnoDB 里面对应一棵 B+ 树。
  2. 执行查询的效率,主键索引>非主键索引>不使用索引
  3. 不适应索引查询,则从B+数的叶子节点遍历
mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中 R1~R5 的 (ID,k) 值分别为 (100,1)、(200,2)、(300,3)、(500,5) 和 (600,6),两棵树的示例示意图如下。
innodb索引组织结构
主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。
非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。

基于主键索引和普通索引的查询有什么区别?
主键索引叶子节点是整行数据,非主键索引叶子节点是主键ID,如果需要查询整行数据,需要根据这个ID再去主键索引树查询一次,这个过程叫回表。

索引维护

B+ 树为了维护索引有序性,在插入新值的时候需要做必要的维护。以上面这个图为例,如果插入新的行 ID 值为 700,则只需要在 R5 的记录后面插入一个新记录。如果新插入的 ID 值为 400,就相对麻烦了,需要逻辑上挪动后面的数据,空出位置。

而更糟的情况是,如果 R5 所在的数据页已经满了,根据 B+ 树的算法,这时候需要申请一个新的数据页,然后挪动部分数据过去。这个过程称为页分裂。在这种情况下,性能自然会受影响。

当然有分裂就有合并。当相邻两个页由于删除了数据,利用率很低之后,会将数据页做合并。合并的过程,可以认为是分裂过程的逆过程。

除了考虑性能外,我们还可以从存储空间的角度来看。假设你的表中确实有一个唯一字段,比如字符串类型的身份证号,那应该用身份证号做主键,还是用自增字段做主键呢?
由于每个非主键索引的叶子节点上都是主键的值。如果用身份证号做主键,那么每个二级索引的叶子节点占用约 20 个字节,而如果用整型做主键,则只要 4 个字节,如果是长整型(bigint)则是 8 个字节。

显然,主键长度越小,普通索引的叶子节点就越小,普通索引占用的空间也就越小。

文章来源:https://blog.csdn.net/qq_51059003/article/details/135552384
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。