1. 1. 一、为什么使用索引
    1. 1.1. 1.什么是索引?
    2. 1.2. 2.为什么使用索引?
    3. 1.3. 2.索引优缺点
  2. 2. 三、索引分类
  3. 3. 四、B+Tree数据库索引原理
    1. 3.1. 什么是局部性原理与磁盘预读?
      1. 3.1.1. 平衡二叉树
      2. 3.1.2. 红黑树
    2. 3.2. B-Tree(有序数组+平衡多叉树)
    3. 3.3. B+Tree(有序数组链表+平衡多叉树)
    4. 3.4. 为什么采用B+Tree?
    5. 3.5. 关于最左前缀原则
    6. 3.6. 计算3层B+Tree能容纳的数据量
    7. 3.7. 回表

一、为什么使用索引

1.什么是索引?

官方对索引的定义为:索引(Index)是帮助 MySQL 高效获取数据的数据结构,数据库索引好比是一本书前面的目录,能加快数据库的查询速度

2.为什么使用索引?

在 MySQL 中,通常有以下两种方式访问数据库表的行数据:

1) 顺序访问

顺序访问是在表中实行全表扫描从头到尾逐行遍历,直到在无序的行数据中找到符合条件的目标数据。这种方式实现比较简单,但是当表中有大量数据的时候,效率非常低下。例如,在几千万条数据中查找少量的数据时,使用顺序访问方式将会遍历所有的数据,花费大量的时间,显然会影响数据库的处理性能。

2) 索引访问

索引访问是通过遍历索引来直接访问表中记录行的方式。使用这种方式的前提是对表建立一个索引,在列上创建了索引之后,查找数据时可以直接根据该列上的索引找到对应记录行的位置,从而快捷地查找到数据。索引存储了指定列数据值的指针,根据指定的排序顺序对这些指针排序。

因为扫描索引的速度一般远远大于扫描实际数据行的速度,所以采用索引的方式可以大大提高数据库的工作效率

2.索引优缺点

优点

  • 极大地加速了索引过程,减少IO次数
  • 创建唯一索引,保证了数据库表中的唯一性
  • 加速了表与表之间的连接
  • 针对分组和排序检索时,能够显著减少查询查询中的分组和排序时间

缺点

  • 索引表占据物理空间
  • 数据表中的数据增加、修改、删除的同时需要去动态维护索引表,降低了数据的维护速度

三、索引分类

1) Hash索引

MySQL 中,只有 MEMORY(MEMORY表只存在内存中,断电会消失,适用于临时表)存储引擎显示支持Hash索引,是 MEMORY 表的默认索引类型,尽管 MEMORY 表也可以使用B+Tree索引。Hash索引把数据以hash形式组织起来,因此当查找某一条记录的时候,速度非常快。但是因为hash结构,每个键只对应一个值,而且是散列的方式分布。所以它并不支持范围查找和排序等功能

2) B+Tree索引

B+Tree是 MySQL 使用最频繁的一个索引数据结构,是 InnoDB 和 MyISAM 存储引擎模式的索引类型。相对 Hash 索引,B+Tree在查找单条记录的速度比不上Hash索引,但是因为更适合排序等操作。

B+Tree 所有索引数据都在叶子节点上,并且增加了顺序访问指针,每个叶子节点都有指向相邻叶子节点的指针。这样做是为了提高区间效率,例如查询key为从18到49的所有数据记录,当找到18后,只要顺着节点和指针顺序遍历就可以以此向访问到所有数据节点,极大提高了区间查询效率大大减少磁盘I/O读取,数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点需要一次I/O就可以完全载

四、B+Tree数据库索引原理

有这么几种树

B-Tree(B Minus Tree)
B+Tree(B Plus Tree)
B*Tree(B Multiply Tree)

B-Tree中的“-”起到的是分隔的作用,并不是“减”的意思。

因此正确的翻译应该是B树,B+树,B*树。而不是B-树,B+树,B*树。因此,当你听到别人说“B减树”的时候,要明白它指的是B-Tree。即B树和B-树是同一种树。

既然知道索引的本质是数据结构,平衡二叉树、红黑树、B-Tree为什么不适合作为索引?

由于索引是存在于索引文件中,是存在于磁盘中的。因为索引通常是很大的,因此无法一次将全部索引加载到内存当中,因此每次只能从磁盘中读取一个磁盘页的数据到内存中。而这个磁盘的读取的速度较内存中的读取速度而言是差了好几个级别

所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数

什么是局部性原理与磁盘预读?

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

平衡二叉树

我们说的平衡二叉树结构,指的是逻辑结构上的平衡二叉树,其物理实现是数组,由于逻辑结构上相近的节点,在物理结构上可能会差很远,因此,每次读取的磁盘页的数据中有许多是用不上的。因此,查找过程中要进行许多次的磁盘读取操作,平衡二叉树没有充分利用磁盘预读功能,所以不适合当索引

红黑树

红黑树也没能利用好磁盘预读的提供的数据(逻辑结构上相近的节点,在物理结构上可能会差很远),并且在大规模数据存储的时候,会出现由于树的深度过大而造成磁盘IO读写过于频繁,所以红黑树也不适合当索引

B-Tree(有序数组+平衡多叉树)

B-Tree的每个节点可以存储多个关键字,它将节点大小设置为磁盘页的大小,充分利用了磁盘预读的功能。每次读取磁盘页时就会读取一整个节点。也正因每个节点存储着非常多个关键字,树的深度就会非常的小。进而要执行的磁盘读取操作次数就会非常少,更多的是在内存中对读取进来的数据进行查找。

模拟查找where id=29过程

  1. 根据首节点找到磁盘块1,读入内存(磁盘I/O操作第1次)
  2. 比较关键字29在的区间(17,35),找到磁盘块1的指针P2
  3. 根据P2指针找到磁盘块3,读入内存(磁盘I/O操作第2次)
  4. 比较关键字29在区间(26,30)找到磁盘块3的指针P2
  5. 根据P2指针找到磁盘块8,读入内存(磁盘I/O操作第3次)
  6. 在磁盘块8中的关键字列表中找到关键字29

B+Tree(有序数组链表+平衡多叉树)

相对于B-Tree来说,B+Tree根节点和子节点只保存了键值和指针,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,这样可以大大加大每个节点存储的key值数量,降低B+Tree的高度,并且B+Tree中的叶子节点比B-Tree多存储了指向下一个叶子节点的指针,这样更方便叶子节点的范围遍历

每个节点占用一个盘块的磁盘空间,一个节点上有两个升序排序的关键字和三个指向子树根节点的指针,两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。以根节点为例,关键字为17和35,P1指针指向的子树的数据范围为小于17,P2指针指向的子树的数据范围为17~35,P3指针指向的子树的数据范围为大于35

为什么采用B+Tree?

数据库索引采用B+Tree的主要原因是:B-Tree在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。而B+Tree只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B-Tree不支持这样的操作(或者说效率太低)

比如说,我们要查找关键字范围在3到7的关键字,在找到第一个符合条件的数字3后,访问完第一个关键字所在的块后,得遍历这个B-Tree,获取下一个块,直到遇到一个不符合条件的关键字。遍历的过程是比较复杂的

相比之下,B+Tree的基于范围的查询简洁很多。由于叶子节点有指向下一个叶子节点的指针,因此从块1到块2的访问,通过块1指向块2的指针即可。从块2到块3也是通过一个指针即可

关于最左前缀原则

有一个复合索引:INDEX(a, b, c)

select * from users where a = 1 and b = 2    能用上a、b
select * from users where b = 3 and a = 1    能用上a、b(有MySQL查询优化器)
select * from users where a = 2 and c = 1    能用上a
select * from users where b = 10 and c = 1    不能

计算3层B+Tree能容纳的数据量

查看MySQL中的页的大小:

InnoDB存储引擎中页的大小为16KB,假如主键ID我们采用BIGINT(8个字节),一条数据大小1KB

第一层可以存储 :
索引键值:(16KB * 1024) / (8B + 6B) = 1170

第二层:

存储索引键:1170^2 = 1368900

如果存储数据:1170 * (16KB / 1KB)= 1368900

第三层
存储数据:1170 * 1170 * 16 = 21902400

回表

就是根据非主键索引查找到根节点,拿到根节点后,再去主键索引中查找相应数据