likes
comments
collection
share

第五章-创建高性能的索引

作者站长头像
站长
· 阅读数 49

——「高性能MYSQL」读书笔记(第五章)

高性能****MYSQL

MYSQL经典书籍,常读常新。

索引的原理

定义问题

根据某个值查找数据,比如 select * from user where id=1234;
根据区间值来查找某些数据,比如 select * from user where id > 1234 and id < 2345

解决问题

引用下数据结构与算法之美的课程

回顾数据结构基础知识

  1. 散列表:散列表的查询性能很好,时间复杂度是 O(1)。但是,散列表不能支持按照区间快速查找数据。所以,散列表不能满足我们的需求

  2. 平衡二叉查找树: 尽管平衡二叉查找树查询的性能也很高,时间复杂度是 O(logn)。而且,对树进行中序遍历,我们还可以得到一个从小到大有序的数据序列,但这仍然不足以支持按照区间快速查找数据。

  3. 跳表:跳表是在链表之上加上多层索引构成的。它支持快速地插入、查找、删除数据,对应的时间复杂度是 O(logn)。并且,跳表也支持按照区间快速地查找数据。我们只需要定位到区间起点值对应在链表中的结点,然后从这个结点开始,顺序遍历链表,直到区间终点对应的结点为止,这期间遍历得到的数据就是满足区间值的数据。

改造二叉查找树

为了让二叉查找树支持按照区间来查找数据,我们可以对它进行这样的改造:树中的节点并不存储数据本身,而是只是作为索引。除此之外,我们把每个叶子节点串在一条链表上,链表中的数据是从小到大有序的。经过改造之后的二叉树,就像图中这样,看起来是不是很像跳表呢?

 第五章-创建高性能的索引

 第五章-创建高性能的索引

改造之后,如果我们要求某个区间的数据。我们只需要拿区间的起始值,在树中进行查找,当查找到某个叶子节点之后,我们再顺着链表往后遍历,直到链表中的结点数据值大于区间的终止值为止。所有遍历到的数据,就是符合区间值的所有数据

新的问题

比如,我们给一亿个数据构建二叉查找树索引,那索引中会包含大约 1 亿个节点,每个节点假设占用 16 个字节,那就需要大约 1GB 的内存空间。给一张表建立索引,我们需要 1GB 的内存空间。如果我们要给 10 张表建立索引,那对内存的需求是无法满足的。如何解决这个索引占用太多内存的问题呢?

把索引存储在硬盘中,而非内存中。我们都知道,硬盘是一个非常慢速的存储设备。通常内存的访问速度是纳秒级别的,而磁盘访问的速度是毫秒级别的。读取同样大小的数据,从磁盘中读取花费的时间,是从内存中读取所花费时间的上万倍,甚至几十万倍

二叉查找树,经过改造之后,支持区间查找的功能就实现了。不过,为了节省内存,如果把树存储在硬盘中,那么每个节点的读取(或者访问),都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。

我们前面讲到,比起内存读写操作,磁盘 IO 操作非常耗时,所以我们优化的重点就是尽量减少磁盘 IO 操作,也就是,尽量降低树的高度。那如何降低树的高度呢?

解决问题

我们来看下,如果我们把索引构建成 m 叉树,高度是不是比二叉树要小呢?如图所示,给 16 个数据构建二叉树索引,树的高度是 4,查找一个数据,就需要 4 个磁盘 IO 操作(如果根节点存储在内存中,其他节点存储在磁盘中),如果对 16 个数据构建五叉树索引,那高度只有 2,查找一个数据,对应只需要 2 次磁盘操作。如果 m 叉树中的 m 是 100,那对一亿个数据构建索引,树的高度也只是 3,最多只要 3 次磁盘 IO 就能获取到数据。磁盘 IO 变少了,查找数据的效率也就提高了。

 第五章-创建高性能的索引

 第五章-创建高性能的索引


/**
 * 这是B+树非叶子节点的定义。
 *
 * 假设keywords=[3, 5, 8, 10]
 * 4个键值将数据分为5个区间:(-INF,3), [3,5), [5,8), [8,10), [10,INF)
 * 5个区间分别对应:children[0]...children[4]
 *
 * m值是事先计算得到的,计算的依据是让所有信息的大小正好等于页的大小:
 * PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
 */
public class BPlusTreeNode {
  public static int m = 5; // 5叉树
  public int[] keywords = new int[m-1]; // 键值,用来划分数据区间
  public BPlusTreeNode[] children = new BPlusTreeNode[m];//保存子节点指针
}

/**
 * 这是B+树中叶子节点的定义。
 *
 * B+树中的叶子节点跟内部节点是不一样的,
 * 叶子节点存储的是值,而非区间。
 * 这个定义里,每个叶子节点存储3个数据行的键值及地址信息。
 *
 * k值是事先计算得到的,计算的依据是让所有信息的大小正好等于页的大小:
 * PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
 */
public class BPlusTreeLeafNode {
  public static int k = 3;
  public int[] keywords = new int[k]; // 数据的键值
  public long[] dataAddress = new long[k]; // 数据地址

  public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点
  public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点
}

对于相同个数的数据构建 m 叉树索引,m 叉树中的 m 越大,那树的高度就越小,那 m 叉树中的 m 是不是越大越好呢?到底多大才最合适呢?不管是内存中的数据,还是磁盘中的数据,操作系统都是按页(一页大小通常是 4KB,这个值可以通过 getconfig PAGE_SIZE 命令查看)来读取的,一次会读一页的数据。如果要读取的数据量超过一页的大小,就会触发多次 IO 操作。所以,我们在选择 m 大小的时候,要尽量让每个节点的大小等于一个页的大小。读取一个节点,只需要一次磁盘 IO 操作。

 第五章-创建高性能的索引

 第五章-创建高性能的索引

尽管索引可以提高数据库的查询效率,但是,作为一名开发工程师,你应该也知道,索引有利也有弊,它也会让写入数据的效率下降。这是为什么呢?数据的写入过程,会涉及索引的更新,这是索引导致写入变慢的主要原因。

总结

数据库索引实现,依赖的底层数据结构,B+ 树。它通过存储在磁盘的多叉树结构,做到了时间、空间的平衡,既保证了执行效率,又节省了内存

特点

  • 每个节点中子节点的个数不能超过 m,也不能小于 m/2;

  • 根节点的子节点个数可以不超过 m/2,这是一个例外;

  • m 叉树只存储索引,并不真正存储数据,这个有点儿类似跳表;

  • 通过链表将叶子节点串联在一起,这样可以方便按区间查找;

  • 一般情况,根节点会被存储在内存中,其他节点存储在磁盘中。

B 树实际上是低级版的 B+ 树,或者说 B+ 树是 B 树的改进版。B 树跟 B+ 树的不同点主要集中在这几个地方:B+ 树中的节点不存储数据,只是索引,而 B 树中的节点存储数据;B 树中的叶子节点并不需要链表来串联。

InnoDB** 的索引模型**

在 InnoDB 中,表都是根据主键顺序以索引的形式存放的,这种存储方式的表称为索引组织表。又因为前面我们提到的,InnoDB 使用了 B+ 树索引模型,所以数据都是存储在 B+ 树中的。

InnoDB存储引擎是 B+ 树索引组织的,所以数据即索引,索引即数据。B+ 树的叶子节点存储的都是数据段的数据。InnoDB 引擎对数据的存储必须依赖于主键,主键对应的索引叫做聚集索引。如果不幸的你建表没有建主键,InnoDB 会从表字段中寻找第一个非空的唯一索引作为聚集索引,如果还是不幸找不到,InnoDB 会生成一个不可见的名为 ROW_ID 的列,该列是一个 6 字节的自增数字,用来创建聚集索引。

每一个索引在 InnoDB 里面对应一棵 B+ 树。

假设,我们有一个主键列为 ID 的表,表中有字段 k,并且在 k 上有索引。

这个表的建表语句是:

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),两棵树的示例示意图如下。

 第五章-创建高性能的索引

图 4 InnoDB 的索引组织结构

从图中不难看出,根据叶子节点的内容,索引类型分为主键索引和非主键索引。

主键索引的叶子节点存的是整行数据。在 InnoDB 里,主键索引也被称为聚簇索引(clustered index)。

非主键索引的叶子节点内容是主键的值。在 InnoDB 里,非主键索引也被称为二级索引(secondary index)。

根据上面的索引结构说明,我们来讨论一个问题:基于主键索引和普通索引的查询有什么区别?

  • 如果语句是 select * from T where ID=500,即主键查询方式,则只需要搜索 ID 这棵 B+ 树;

  • 如果语句是 select * from T where k=5,即普通索引查询方式,则需要先搜索 k 索引树,得到 ID 的值为 500,再到 ID 索引树搜索一次。这个过程称为回表。

也就是说,基于非主键索引的查询需要多扫描一棵索引树。因此,我们在应用中应该尽量使用主键查询。

索引的优点

索引按照顺序存储数据,可以做Order By 和Group by 的操作。

  • 索引减少服务器需要扫描的数据量

  • 帮助服务器避免排序和临时表

  • 随机I/O变成顺序IO

索引的适用

小表不合适,中到大型表有效,特大型的表,建立索引代价增长。建立元数据信息表。Infobright实现。

高性能索引策略

高效选择和使用索引有很多种方式,有针对特殊案例的优化方法,有针对特定行为的优化,使用哪个索引,如何评估选择不同索引的性能影响技巧,需要持续不断的学习

反模式

  • 过滤使用函数,Mysql无法使用方程式。简化Where,索引列需要独立

  • 为每个列创建独立的索引,或者按照错误的顺序创建多列索引。

  • 避免随机的聚簇索引,特别是IO密集型,例如UUID作为索引,插入完全随机,不仅主键长,而且页分裂和碎片

  • 不用覆盖索引做延迟关联

部分读书思考

  • B-Tree作为经典的关系型数据库的解决方案,理解其原理需要其解决的问题着手,其解决问题的过程也是架构设计权衡的一次经典案例,其他引擎Infrobright,Memory等。

  • 数据的模型、存储、查询经历了从文档数据库到关系型数据库的演变,每种数据库都有其特定的应用场景和权衡思考。使用 Mysql 时需要考虑好场景,同时可以混合目前各种存储系统进行组合使用。

  • 审批的数据库使用 Sql 查询相对都是单表查询,面临的问题挑战不大,不过也有部分需要优化。值得思考点可能是 ORM 使用上可是否可以借鉴 Mybatis 的一些缓存的思路,提升整体性能。

拓展阅读

  1. 数据库的简单实现:www.ruanyifeng.com/blog/2014/0…;

  2. 数据密集型应用系统设计,比较经典。

  3. www.codedump.info/#about

转载自:https://juejin.cn/post/7182842594253094968
评论
请登录