数据库 MYSQL 事物

数据库原理篇(1)

索引的实现原理

Posted by Jason Lee on 2019-09-04

索引概诉

索引详解

常见的索引算法

平衡二叉树索引

二叉树的查找的时间复杂度是O(log2N)，其查找效率与深度有关，而普通的二叉树可能由于内部节点排列问题退化成链表，这样查找效率就会很低。因此平衡二叉树是更好的选择，因为它保持平衡，即通过旋转调整结构保持最小的深度。其查找的时间复杂度也是O(log2N)。

但实际上，数据库中索引的结构也并非AVL树或更优秀的红黑树，尽管它的查询的时间复杂度很低。

那为什么平衡二叉树不适合作为索引呢？

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

注意，我们说的平衡二叉树结构，指的是逻辑结构上的平衡二叉树，其物理实现是数组。然后由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此，每次读取的磁盘页的数据中有许多是用不上的。因此，查找过程中要进行许多次的磁盘读取操作。

而适合作为索引的结构应该是尽可能少的执行磁盘IO操作，因为执行磁盘IO操作非常的耗时。因此，平衡二叉树并不适合作为索引结构。

为什么 二叉树物理结构上可能相差很远？

举个例子：

二叉树就物理结构来分可以分成：顺序存储结构和链式存储结构。

  • 1. 顺序存储结构：

    顺序存储结构，顾名思义就是二叉树的数据元素存放在一组连续的存储单元中。其主要有一下几个特点：

    • ① 逻辑上相邻的两个元素在物理位置上也是相邻的；

    • ② 操作删除和插入的时候，需要整体移动元素；

    • ③ 需要预先分配空间，不能动态增长；

      例如：

下标 1 2 3 4 5 6 7 8 9 10
下标 A B C D E F G H I J

  • 1. 链式存储结构：

    链式存储结构中二叉树的每个结点至少包含三个域：数据域、左指针域和右指针域。其二叉树是通过指针实现，链式存储结构有以下几个特点：

    • ① 逻辑上相邻的两个元素在物理位置上不一定是相邻的；

    • ② 操作删除和插入的时候，不需要整体移动元素；只需要修改相应的指针即可；

    • ③ 不需要预先分配空间；

    • ④ 存储指针本身会消耗一定的存储的空间；

      基本数据如下：

下标 左孩子 数据 右孩子
left_child data right_child

树的保存如下：

由于索引是有序的， 所有我们可以假定 左子树小于右子树
即 B < A < C ， D < B < E

如果也强制用数组表示的话：如下（0 表示为空）

下标 1 2 3 4 5 6 7 8 9 10
(2,A,3) (4,B,5) (6,C,7) (8,D,9) (10,E,0) (0,F,0) (0,G,0) (0,H,0) (0,I,0) (0,J,0)

所有,如果我要查找H 这个字符，当我们判断到到 H < D 的时候，因为H D相差不是很大， 但是在数组存贮相差甚远。

所以当我们加载 1 - 6 的数据块的时候，H所在的 7 - 10 数据库就无法加载到内存当中。 所以，当找到D 的时候，我们需要再次进行一次io 将7 - 10 的数据块加载到内存当中。额外消耗了一次io。

B树索引

B树是平衡多叉树，解决了查找深度的问题。红黑树（平衡二叉树）没能充分利用磁盘预读功能，而B树是为了充分利用磁盘预读功能来而创建的一种数据结构，也就是说B树就是为了作为索引才被发明出来的的。

局部性原理与磁盘预读：

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

程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。

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

B 树的索引结构：

B+树的索引

B+树的关键字全部存放在叶子节点中，非叶子节点用来做索引，而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据

B+树索引结构

B+树索引 VS B树索引

  • B树必须用中序遍历的方法按序扫库。
  • 而B+树直接从叶子结点挨个扫一遍就完了，
  • B+树支持range-query非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
  • B+树非叶子节点不存数据，这样可以使得每一页能存贮更多的索引，是的树高减少。

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

索引的种类

按照索数据的组织方式，我们可以分聚簇索引，非聚簇索引（辅助索引）
按照索引的作用 可以分为 主键索引，唯一索引，单建索引，复合索引，全文索引等。

主键索引

  • 概念：主键索引是唯一的，通常以表的ID设置为主键索引,一个表只能有一个主键索引，这是他跟唯一索引的区别。

在 InnoDB 内部，表数据是优化主键快速查询而排列分布的，其查找速度是最快的，该索引中键值的逻辑顺序决定了表中相应行的物理顺序。即使表中没有适合做主键的列，也推荐采用一个自动增长的整数主键(代理键)，那么这个表在增加数据的时候是顺序存放的，而且后续在别的表参考该外键查询的时候也会得到优化。

  • 主键的选择：

    • 显示的定义主键
    • 如果没有，则非空的唯一索引（Unique NOT NULL
    • InnoDB 存储引擎自动创建一个 6 个字节大小的指针，用户不能查看或访问。

  • 主键的插入：
    主键的推荐是使用自增的ID, 自增 ID 在插入的时候可以保证相邻的两条记录可能在同一个数据块,在插入的时候，由于要维持id的有序性，当自增的ID在物理上也连续，那么可以有效的减少磁盘块的加载次数。

1
2
3
4
create table User(
`uid` int,
 primary key(`uid`)
);

唯一索引

  • 概念：唯一索引主要用于业务上的唯一约束
  • 和主键的区别：他跟主键索引的区别是，一个表可以有多个唯一索引
  • 创建语句：
1
2
3
4
5
create table User(
`uid` int,
`age` int,
 unique key(`uid`)
);

单键索

  • 概念：以某一个字段为索引
1
2
3
4
5
create table User(
`uid` int,
`age` int,
 unique key(`uid`)
);

联合索引

  • 概念：两个或两个以上字段联合组成一个索引
  • 比如我们有表 如下
1
2
3
4
5
create table User(
`a` int,
`b` int,
 unique key(`uid`)
);

我们可以看到， 联合索引的结构依然是一个B+ 数的结构，只不过每一个节点存放的值并不是单个值，而是多个值。 节点的排序是先按照第一个索引的顺存放，然后再按照第二个索引大小的值存放，因此在叶子节点的排列应该是

> (1,1) (1, 2) (2, 1) (2, 4) (3,1) (3,2)

  • 最左前缀

    因此 对于查询

    SELECT * FROM USER where a=xxx and b=xxx

    我们当然可以通过索引查找对应的数值，因为 a最左边的索引，如果我们想要查
    SELECT * FROM USER where b=xxx 的时候，我们发现 b 在两个叶子节点数据分别为 1 2 1 和 4 1 3 完全无序， 那么因此，就不可以索引查询。因此这句话的查询索引就失效了。

    这就是最左匹配原则。

  • 上述的联合索引还有什么好处。因为我们的a b 是联合有序，那么在a 已经确定的情况下，我们可以直接利用索引，返回b的有序结合，不需要额外的二次排序。
    比如如下语句

    SELECT * FROM USER where a=xxx order by b desc limit 3

    在a确定的情况下 b 已经是有序的了，所以不需要回表查询。

全文索引

通过数值比较、范围过滤等就可以完成绝大多数我们需要的查询，但是，如果希望通过关键字的匹配来进行查询过滤，那么就需要基于相似度的查询，而不是原来的精确数值比较。全文索引就是为这种场景设计的。
开始之前，先说一下全文索引的版本、存储引擎、数据类型的支持情况
MySQL 5.6 以前的版本，只有 MyISAM 存储引擎支持全文索引；
MySQL 5.6 及以后的版本，MyISAM 和 InnoDB 存储引擎均支持全文索引;
只有字段的数据类型为 char、varchar、text 及其系列才可以建全文索引。
测试或使用全文索引时，要先看一下自己的 MySQL 版本、存储引擎和数据类型是否支持全文索引。

索引的使用场景

  1. 当数据多且字段值有相同的值得时候用普通索引。
  2. 当字段多且字段值没有重复的时候用唯一索引。
  3. 当有多个字段名都经常被查询的话用复合索引。
  4. 普通索引不支持空值，唯一索引支持空值。
  5. 但是，若是这张表增删改多而查询较少的话，就不要创建索引了，因为如果你给一列创建了索引，那么对该列进行增删改的时候，都会先访问这一列的索引，
  6. 若是增，则在这一列的索引内以新填入的这个字段名的值为名创建索引的子集，
  7. 若是改，则会把原来的删掉，再添入一个以这个字段名的新值为名创建索引的子集，
  8. 若是删，则会把索引中以这个字段为名的索引的子集删掉。
  9. 所以，会对增删改的执行减缓速度，
  10. 所以，若是这张表增删改多而查询较少的话，就不要创建索引了。
  11. 更新太频繁地字段不适合创建索引。
  12. 不会出现在where条件中的字段不该建立索引。

索引组织方式：

  • 聚簇索引

InnoDB 可以看做是聚集索引，因为它的 B+ 树的叶结点包含了完整的数据记录。InnoDB 的数据文件本身就是索引文件，表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说，InnoDB 的所有辅助索引都引用主键作为 data 域。

  • 非聚簇索引（辅助索引）

而 MyISAM 方式 B+ 树的叶结点只是存储了数据的地址，故称为非聚集索引。MyISAM 引擎使用 B+Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址；在 MyISAM 中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。

区别和用法

聚簇索引根据主键来构建，叶子节点存放的是该主键对应的这一行记录，根据主键查询可以直接利用聚簇索引定位到所在记录。

而普通索引根据申明这个索引时候的列来构建，叶子节点存放的是这一行记录对应的主键的值，根据普通索引查询需要先在普通索引上找到对应的主键的值，然后根据主键值去聚簇索引上查找记录，俗称回表。 如果我们查询一整行记录的话，一定要去聚簇索引上查找，而如果我们只需要根据普通索引查询主键的值，由于这些值在普通索引上已经存在，所以并不需要回表，这个称为索引覆盖，在一定程度上可以提高查询效率。

参考


赏 支付宝打赏 微信打赏

赞赏一下



FEATURED TAGS
数据库 MYSQL 事物
FRIENDS