您的位置: 首页  >  文章  >  MySQL索引的实现和原理

MySQL索引的实现和原理

分类: 文章 • 2023-01-06 14:51:30

以下部分内容整理自其它博客

记录下来以供复习

话说CSDN不支持markdown真的不开心

索引

分类

索引按种类分为主键索引，唯一索引，普通索引 
按数据结构分为B+树索引和哈希索引 
按创建类型分聚簇索引和非聚簇索引

聚簇索引就是以主键创建的索引 
非聚簇索引就是以非主键创建的索引 
聚簇索引在叶子节点存储的是表中数据，非聚簇存的是主键和索引列 
非聚簇查询时，拿到主键再去查找想要的数据（回表）

基本概念

首先我们要知道数据库是如何存储数据的

MySQL索引的实现和原理

上面的图片代表一页 
每个数据页组成一个双向链表 
而每个数据页中的记录又组成一个单向链表 
其中每一页都会根据主键生成一个页目录，可利用二分法快速定位 
以其他列做搜索条件时只能从最小记录开始依次遍历，检索每一页

因此，索引的作用体现于此

索引的实现

举个栗子 
一个可能的索引

MySQL索引的实现和原理

时间复杂度：O(log2N)

B-Tree

层：d，为大于1的正整数 
高度：h 
每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d 
每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 
所有叶子节点具有相同的深度，等于树高h 
key和指针相互间隔，节点两端是指针 
一个节点中的key从左到右非递减排列

MySQL索引的实现和原理

查找算法：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。

 

BTree_Search(node, key) {

if(node == null) return null;

foreach(node.key)

{

if(node.key[i] == key) return node.data[i];

if(node.key[i] > key) return BTree_Search(point[i]->node);

}

return BTree_Search(point[i+1]->node);

}

data = BTree_Search(root, my_key);

时间复杂度：O(logdN)

for example：

MySQL索引的实现和原理

  1. 根据根结点指针找到文件目录的根磁盘块1，将其中的信息导入内存。【磁盘IO操作 1次】
  2. 此时内存中有两个文件名17、35和三个存储其他磁盘页面地址的数据。根据算法我们发现：17<29<35，因此我们找到指针p2。
  3. 根据p2指针，我们定位到磁盘块3，并将其中的信息导入内存。【磁盘IO操作 2次】
  4. 此时内存中有两个文件名26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现：26<29<30，因此我们找到指针p2。
  5. 根据p2指针，我们定位到磁盘块8，并将其中的信息导入内存。【磁盘IO操作 3次】
  6. 此时内存中有两个文件名28，29。根据算法我们查找到文件名29，并定位了该文件内存的磁盘地址。

B+树 
B+树是B树的变种 
不同点：

每个节点的指针上限为2d而不是2d+1 
内节点不存储data，只存储key，叶子节点不存储指针

MySQL索引的实现和原理

for example

MySQL索引的实现和原理

查找id为8的记录

  1. 在页33中，算法比较得到 1< 8 < 320，30页保存1-320的数据
  2. 进入页30，5 < 8 < 12，28页保存5-12的数据
  3. 进入页28，找到记录8

Hash索引 
时间复杂度O(1) 
方式：通过哈希算法来定位数据

MySQL索引的实现和原理

缺点：

哈希索引没法利用索引完成排序（键值是不规律的） 
不支持最左匹配原则 
在大量重复键值情况下哈希索引效率极低 
不支持范围查询

性能分析 
局部性理论 
当一个数据被用到时，其附近的数据也通常会马上被使用

因此，为了提高效率，尽量减少磁盘I/O，磁盘会从读取字节开始顺序向后读取一定长度的数据放入内存

磁盘模型

MySQL索引的实现和原理

可以使用I/O次数来评价索引结构的优劣

  • B树一个节点大小设为一个页，这样每个节点依次I/O就能完全载入。
  • B树一次检索最多h-1次I/O，渐进复杂度为O(h)=O(logdN)
  • 红黑树这类的二叉树结构h较大，逻辑上近的节点（父子）物理上可能很远，无法利用局部性，渐进复杂度为O(h)，效率较B树差很多
  • B+树内节点不储存data，同空间可以存放更多的节点，因此性能更优

MyIsam索引实现

MySQL索引的实现和原理 
data域存放的是数据记录的地址，索引文件和数据文件是分离的 
其中主索引和辅索引在结构上没任何区别，只是辅索引key可以重复 
这种索引方式也叫“非聚集”

InnoDB索引实现 
数据文件本身就是索引文件，索引B+树的叶节点data域保存了完整的数据记录，key是主键

这中索引叫聚集索引

MySQL索引的实现和原理 
因此，InnoDB必须要有主键（MyIsam可以没有），若未显示指定，自动选择可以唯一标识的列做主键，若不存在，MySQL自动生成隐含字段做主键

辅助索引data域记录的是主键的值而不是地址

MySQL索引的实现和原理 
辅助索引需要检索两遍索引，先检索辅助索引找到主键，然后通过主键获取记录（回表）

B+树索引 
时间复杂度**O(logn) 
方式：利用B+树的优点快速查找对应记录 
用处：常用于数据库和操作系统的文件系统中

B+树是对B树的一种变种树，它与B树的差异在于：

  • 有k个子结点的结点必然有K个关键码
  • 非叶子结点具有索引作用，跟记录有关的信息均存放在叶子结点
  • 树的所有叶子结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录

B+树的优点在于：

  • 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
  • B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

为什么采用B+树而不是B树或二叉树

  • B+树空间利用率更高，非叶子节点不存信息，同样存储空间能放下更多指针，减少IO次数
  • B+树IO效率更高，增删节点时效率更高
  • 查询效率更稳定

eg: select * from user where username=’abc’ and sex=1;

这种情况下如何建索引？索引的顺序？

使用explain分析SQL执行效率

覆盖索引&&最左匹配原则 
当匹配联合索引遇到范围查询时就会停止匹配

自动优化顺序 
不需要考虑=、in等的顺序，mysql会自动优化这些条件的顺序，以匹配尽可能多的索引列

eg: 
titles表 
有主索引<emp_no,title,from_date>

key_len计算规则

  1. 所有的索引字段，如果没有设置not null，则需要加一个字节。
  2. 定长字段，int占四个字节、date占三个字节、char(n)占n个字符。
  3. 对于变成字段varchar(n)，则有n个字符+两个字节。

  4. 不同的字符集，一个字符占用的字节数不同。latin1编码的，一个字符占用一个字节，gbk编码的，一个字符占用两个字节，utf8编码的，一个字符占用三个字节。

    • 全列匹配 
      EXPLAIN SELECT * FROM employees.titles WHERE emp_no=’10001’ AND title=’Senior Engineer’ AND from_date=’1986-06-26’; 
      +—-+————-+——–+——-+—————+———+———+——————-+——+——-+ 
      | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | 
      +—-+————-+——–+——-+—————+———+———+——————-+——+——-+ 
      | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | | 
      +—-+————-+——–+——-+—————+———+———+——————-+——+——-+

如果颠倒where的顺序，效果一样

  • 最左前缀匹配 
    EXPLAIN SELECT * FROM employees.titles WHERE emp_no=’10001’; 
    +—-+————-+——–+——+—————+———+———+——-+——+——-+ 
    | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | 
    +—-+————-+——–+——+—————+———+———+——-+——+——-+ 
    | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | | 
    +—-+————-+——–+——+—————+———+———+——-+——+——-+ 
    只用到了索引第一列

如果where中只有emp_no和from_date，那么也只会使用第一列

可以使用辅助索引<emp_no,from_date> 或者 用‘in’来填补

  • 查询条件没有指定第一列 
    EXPLAIN SELECT * FROM employees.titles WHERE from_date=’1986-06-26’; 
    +—-+————-+——–+——+—————+——+———+——+——–+————-+ 
    | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | 
    +—-+————-+——–+——+—————+——+———+——+——–+————-+ 
    | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where | 
    +—-+————-+——–+——+—————+——+———+——+——–+————-+ 
    这种情况无法使用索引

  • 通配符%不出现在开头则可以用到索引

  • 索引最多作用于一个范围列
  • 查询条件中含有函数或表达式则不会使用索引

索引总结

  • 最左匹配原则
  • 尽量选择区分度高的列作为索引
  • 索引列不能参与计算
  • 尽可能扩展索引而不是新建索引
  • 单个多列组合索引和多个单列组合索引检索查询效果不同
  • 索引本身也是有代价的，消耗存储空间，降低增删改效率

相关推荐