本文内容主要来源于网络主流文章。仅根据个人理解稍加整合,最后附有参考链接。
1. 摘要
本文以MySQL数据库为研究对象,讨论数据库索引相关的一些话题。需要注意的是,MySQL支持多种存储引擎,各种存储引擎对索引的支持也不同。因此,MySQL数据库支持多种索引类型,比如BTree索引、哈希索引、全文索引等。为了避免混淆,本文将只关注BTree索引,因为这是主要处理的索引使用 MySQL 时与。至于哈希索引和全文索引,本文暂时不讨论。
2. 常用查询算法和数据结构
为什么这里需要讲查询算法和数据结构呢?因为建立索引的原因实际上是为了构建一个可以应用高效查询算法的数据结构,最终提高数据的查询速度。
2.1 指数的性质
MySQL官方对索引的定义是:索引(Index)是一种帮助MySQL高效获取数据的数据结构。通过提取句子主干,就可以得到索引的本质:索引是一种数据结构。
2.2 常用查询算法
我们知道数据库查询是数据库最重要的功能之一。我们都希望能够尽可能快地查询数据,因此数据库系统的设计者会从查询算法的角度进行优化。那么什么查询算法可以让查询速度更快呢?
2.2.1 顺序查找( )
最基本的查询算法当然是顺序搜索( ),它是一种对每个元素进行比较的方法。但当数据量很大时,该算法效率极低。
示例代码:
//顺序查找
int SequenceSearch(int a[], int value, int n)
{
int i;
for(i=0; i
if(a[i]==value)
return i;
return -1;
}
2.2.2 二分查找 ( )
比顺序搜索更快的查询方法应该是二分搜索。二分查找的原理是从数组的中间元素开始查找。如果中间元素恰好是要查找的元素,则查找过程结束;如果某个元素大于或小于中间元素,则在数组中查找大于或小于中间元素的一半,并像以前一样从中间元素开始比较。如果到了某步数组为空,则说明找不到。
示例代码:
//二分查找,递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
int mid = low+(high-low)/2;
if(a[mid]==value)
return mid;
if(a[mid]>value)
return BinarySearch2(a, value, low, mid-1);
if(a[mid]<value)
return BinarySearch2(a, value, mid+1, high);
}
2.2.3 二叉排序树搜索
二叉排序树的特点是:
搜索的工作原理:
2.2.4 Hash散列方法(哈希表)
其原理是首先根据键值和哈希函数创建一个哈希表(哈希表),然后根据键值和哈希函数定位数据元素的位置。
2.2.5 块搜索
分块搜索也称为索引顺序搜索,它是顺序搜索的改进方法。算法思想是将n个数据元素“按块顺序”划分为m个块(m≤n)。每个块中的节点不必按顺序排列,但块之间必须“按块排序”;即第一个块中任意元素的键必须小于第二个块中任意元素的键;并且块 2 中的任何元素都必须小于块 3 中的任何元素,依此类推。
算法流程:
首先选择每个块中最大的关键字,形成索引表;
查找分为两部分:首先对索引表进行二分查找或顺序查找,确定要查找的记录在哪个块;然后,使用顺序方法在确定的块中进行搜索。
该搜索算法每次比较都会将搜索范围缩小一半。它们的查询速度得到了很大的提高,而且它们的复杂度也得到了很大的提高。如果你稍微分析一下,你会发现每种搜索算法都只能应用于特定的数据结构。比如二分查找要求检索到的数据是有序的,而二叉树查找只能适用于二叉查找树,但是数据本身的组织结构并不能完全满足各种数据结构(比如理论上不可能同时组织两者)列同时按顺序排列),因此除了数据之外,数据库系统还维护满足特定搜索算法的数据结构。结构以某种方式引用(指向)数据,允许在这些数据结构上实现高级搜索算法。这个数据结构就是索引。
2.3 平衡多路径搜索树B树(B-tree)
前面提到,二叉树的搜索时间复杂度为O(log2N),因此它的搜索效率与树的深度有关。如果要提高查询速度,就必须减少树的深度。要减少树的深度,一种自然的方法是使用多叉树。结合平衡二叉树的思想,我们可以构建平衡多叉树结构,然后在其上构建平衡多路径搜索算法,以提高对大量数据的处理。搜索效率。
2.3.1 B树
B-tree也叫B树(实际上B-是从B-tree翻译过来的,所以B-tree和B-tree是同一个概念)。它是一个平衡的多路径搜索树。下图是典型的B树:
从上图我们可以大致看出B树的一些特点。为了更好地描述B树,我们将记录定义为元组[key, data],其中key是记录的键值,data代表其他数据(上图)。图中只有按键,没有显示数据)。下面是B树的详细定义:
1、存在根节点,且根节点只有一条记录和两个子节点或者根节点为空;
2、每个节点记录中的key和指针相互间隔,指针指向子节点;
3. d表示树的宽度。除叶子节点外,其他每个节点都有[d/2,d-1]条记录,这些记录中的键从左到右按大小排列。有[d/2+1,d]个孩子;
4. 在一个节点中,第n个子树中的所有键都小于该节点中的第n个键并且大于第n-1个键。例如上图中节点B的第二个子节点E中的所有键均小于B中的第二个键9且大于第一个键3;
5、所有叶子节点必须处于同一级别,即深度相同;
由于B-Tree的特点,B-Tree中通过key检索数据的算法非常直观:首先从根节点开始进行二分查找,如果找到则返回对应节点的数据,否则递归查找相应区间的指针所指向的节点。 ,直到找到节点或者找到空指针,前者成功,后者失败。 B-Tree上的搜索算法伪代码如下:
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)
B-Tree 有一系列有趣的属性。例如,如果度为 d 的 B-Tree 有 N 个键作为索引,则其树高 h 的上限为 logd((N+1)/2)。如果检索一个键,查找节点数的渐近复杂度为 O(logdN)。从这一点可以看出B-Tree是一种非常高效的索引数据结构。
另外,由于插入和删除新的数据记录会破坏B-Tree的属性,因此在插入和删除时,需要对树进行拆分、合并、转移等操作来保持B-Tree的属性。本文不打算全面讨论B-Tree。因为已经有很多资料详细描述了B-Tree的数学性质和插入删除算法,有兴趣的朋友可以查阅其他文献进行详细研究。
2.3.2 B+树
事实上,B-Tree有很多变体,其中最常见的是B+Tree。例如,MySQL一般采用B+Tree来实现其索引结构。与B-Tree相比,B+Tree有以下区别:
下面是一个简单的B+Tree图。
由于并非所有节点都具有相同的域,因此 B+Tree 中的叶节点和内部节点通常具有不同的大小。这与B树不同。虽然B-Tree中不同节点存储的键和指针的数量可能不一致,但每个节点的域和上限是一致的。因此,在实现中,B-Tree往往对每个节点都同等适用。空间的大小。一般来说,B+Tree比B-Tree更适合实现外部存储索引结构。具体原因与外部存储器和计算机访问的原理有关,下面将讨论。
2.3.3 具有顺序访问指针的B+树
数据库系统或文件系统中普遍使用的B+Tree结构,是在经典B+Tree的基础上进行优化,增加了顺序访问指针。
如图所示,在B+Tree的每个叶子节点中添加指向相邻叶子节点的指针,就形成了顺序访问指针的B+Tree。本次优化的目的是提高区间访问的性能。例如图4中,如果要查询key为18到49的所有数据记录,找到18后,只需要依次遍历节点和指针即可一次性访问完毕。到所有数据节点,大大提高区间查询的效率。
本节简要介绍B-Tree和B+Tree。下一节结合内存访问的原理来介绍为什么B+Tree是目前数据库系统中索引的首选数据结构。
3、索引数据结构设计相关的计算机原理
前面提到,二叉树、红黑树等数据结构也可以用来实现索引,但文件系统和数据库系统一般采用B-/+Tree作为索引结构。本节将基于有关计算机组成原理的知识来讨论B-。 /+树作为索引的理论基础。
3.1 两种存储类型
计算机系统一般包括两种类型的存储,计算机主存储器(RAM)和外部存储器(例如硬盘、CD、SSD等)。在设计索引算法和存储结构时,必须考虑到这两类存储的特点。主存储器读取速度快。与主存相比,外置磁盘的数据读取速度比主从慢几个数量级。它们之间的具体区别稍后会详细介绍。上面提到的所有查询算法都假设数据存储在计算机的主存中。计算机的主存一般都比较小。在实际的数据库中,数据存储在外部存储器中。
一般来说,索引本身也很大,无法完全存储在内存中,因此索引往往以索引文件的形式存储在磁盘上。这种情况下,索引查找过程中会产生磁盘I/O消耗。与内存访问相比,I/O 访问的消耗要高几个数量级。因此,评价一个数据结构作为索引的好坏最重要的指标就是搜索过程中磁盘I/O操作次数的渐近复杂度。换句话说,索引的结构组织应该尽量减少搜索过程中磁盘I/O 访问的次数。下面详细介绍内存和磁盘访问的原理,然后结合这些原理来分析B-/+Tree作为索引的效率。
3.2 主存访问原理
目前,计算机中使用的主存储器基本上是随机读写存储器(RAM)。现代RAM的结构和存取原理都比较复杂。本文抛开具体差异,抽象出一个非常简单的访问模型来说明RAM的工作原理。
从抽象的角度来看,主存是由一系列存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元都有一个唯一的地址。现代主存的寻址规则相对复杂。这里将它们简化为二维地址:通过行地址和列地址可以唯一定位一个存储单元。上图显示了 4 x 4 主存模型。
主存的访问过程如下:
当系统需要读取主存时,将地址信号放在地址总线上,传输到主存。主存读取地址信号后,解析该信号并定位到指定的存储单元,然后将该存储单元的数据放到数据总线上。 ,供其他组件读取。写入主存的过程类似。系统将要写入的单元的地址和数据分别放置在地址总线和数据总线上。主存读取两条总线的内容并进行相应的写操作。
这里可以看出,主存访问的时间仅与访问次数呈线性关系。因为没有机械操作,所以两次访问数据的“距离”不会对时间产生任何影响。例如先取A0,再取A0。 A1与先取A0再取D3的耗时相同。
3.3 磁盘访问原理
如上所述,索引一般以文件的形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O涉及机械运动成本,因此磁盘I/O的时间消耗是巨大的。
从磁盘读取数据依赖于机械运动。当需要从磁盘读取数据时,系统会将数据的逻辑地址传输到磁盘。磁盘的控制电路会根据寻址逻辑将逻辑地址翻译为物理地址,即确定要读取的数据。数据在哪个磁道、哪个扇区。为了读取该扇区中的数据,需要将磁头放置在该扇区上方。为了实现这一点,磁头需要移动以与相应的磁道对齐。这个过程称为寻道,所花费的时间称为寻道时间。然后磁盘旋转将目标扇区在磁头下旋转。这个过程所花费的时间称为轮转时间,最后将读取的数据传输出去。因此,每次读取数据所花费的时间可以分为三个部分:寻道时间、旋转延迟和传输时间。在:
那么访问一个磁盘的时间,也就是一次磁盘IO的时间大约等于5+4.17=9ms,听起来还不错,但是要知道一台500-MIPS的机器每秒可以执行5亿条指令,因为指令依赖于电的性质。也就是说,执行一次IO的时间内可以执行40万条指令。数据库往往包含数十万、数百万甚至数千万的数据。每次都需要9毫秒,这显然是一场灾难。
3.4 局部性原理和磁盘预读
由于存储介质的特性,磁盘访问速度比主存慢得多。再加上机械运动的成本,磁盘访问速度往往是主存的百分之一。因此,为了提高效率,需要尽可能减少磁盘数量。输入/输出。为了达到这个目的,磁盘往往并不是严格按需读取,而是每次都提前读取。即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据到内存中。其理论基础是计算机科学中众所周知的局部性原理:当使用一条数据时,通常会立即使用附近的数据。程序执行过程中所需的数据通常比较集中。
由于顺序磁盘读取非常高效(无寻道时间,旋转时间极少),因此预读可以提高具有局部性的程序的 I/O 效率。预读长度一般为页的整数倍。页是计算机管理的内存的逻辑块。硬件和操作系统通常将主存和磁盘存储区域划分为连续的相同大小的块。每个存储块称为页(在许多操作系统中,页大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,就会触发缺页异常。这时,系统会向磁盘发出读信号,磁盘会找到数据的起始位置,向后读取一页或多页。加载到内存中,然后异常返回,程序继续运行。
4.数据库索引中使用的数据结构B-/+Tree及其性能分析
至此我们终于可以分析一下为什么数据库索引采用B-/+Tree存储结构了。前面提到,数据库索引存储在磁盘上,我们一般用磁盘I/O的次数来评价索引结构的好坏。我们先从B-Tree分析开始。根据B-Tree的定义,可以看出一次检索最多需要访问h-1个节点(根节点常驻内存)。数据库系统的设计者巧妙地利用了磁盘预读原理,将一个节点的大小设置为一页,这样每个节点只需一次I/O就可以满载。为了达到这个目标,在B-Tree的实际实现中需要用到以下技术:每次创建新节点时,直接申请一页空间。这确保节点物理存储在页面中。另外,计算机存储分配是按页对齐的,一个节点只需要一次I/O。
B-Tree 中的一次检索最多需要 h-1 个 I/O(根节点驻留在内存中),渐进复杂度为 O(h)=O(logdN)。一般实际应用中,出度d是一个很大的数,通常大于100,因此h很小(通常不超过3)。
综上所述,如果我们使用B-Tree存储结构,搜索时的I/O次数一般不会超过3次,因此使用B-Tree作为索引结构是非常高效的。
4.1 B+树性能分析
从上面的介绍我们知道B树的搜索复杂度为O(h)=O(logdN),所以树的出度d越大,深度h越小,树的个数也越少I/O。 B+Tree正好可以增加出度d的宽度,因为每个节点都是一页大小,所以出度上限取决于节点中key和数据的大小:
dmax=floor(pagesize/(keysize+datasize+pointsize))//floor表示向下取整
由于B+Tree中的节点去掉了数据域,因此它们可以具有更大的出度,从而具有更好的性能。
4.2 B+树搜索过程
B-树和B+树的搜索过程基本相同。如上图所示,如果要查找数据项29,首先将磁盘块1从磁盘加载到内存中。这时候就发生IO了。在内存中使用二分查找,确定29在17到35之间,锁定磁盘块1。P2指针,内存时间可以忽略不计,因为它很短(与磁盘IO相比),磁盘块3从加载通过磁盘块1的P2指针的磁盘地址到内存,第二次IO发生,29处26和30,磁盘块3的P2指针被锁定,磁盘块8通过磁盘块加载到内存中指针。第三次IO发生。同时在内存中进行二分查找,找到29,查询结束。总共三个IO。真实情况是3层b+树可以表示数百万数据。如果百万级数据搜索只需要3次IO,性能提升将是巨大的。如果没有索引,则每个数据项都会发生一次IO。 ,那么总共需要数百万次IO,这显然是非常非常昂贵的。
本章从理论角度讨论与索引相关的数据结构和算法问题。下一章将讨论B+Tree在MySQL中具体是如何实现为索引的。同时,将结合InnDB存储引擎同时引入非聚集索引和聚集索引。不同的索引实现。
5.MySQL索引实现
在MySQL中,索引是一个存储引擎级别的概念,不同的存储引擎对索引的实现方式不同。本文主要讨论两种存储引擎的索引实现方法。
5.1 索引实现
引擎采用B+Tree作为索引结构,叶子节点的data域存储数据记录的地址。下图是索引的示意图:
假设该表总共有三列。假设我们使用 Col1 作为主键。上图显示了表的主索引(键)。可见索引文件只保存了数据记录的地址。中,主索引和辅助索引(键)没有结构上的区别,只是主索引要求键唯一,而辅助索引的键可以重复。如果我们在Col2上创建一个辅助索引,这个索引的结构如下图:
它也是一棵B+Tree,数据字段存储的是数据记录的地址。因此,索引检索的算法是首先按照B+Tree搜索算法来搜索索引。如果指定的Key存在,则取出其数据字段的值,然后以数据字段的值作为地址读取对应的数据记录。
索引方法也称为“非聚集”。之所以这么称呼,是为了与聚集索引区分开来。
5.2 指数实现
虽然同样采用B+Tree作为索引结构,但具体实现却完全不同。
第一个大的区别是数据文件本身是索引文件。从上面我们知道,索引文件和数据文件是分开的,索引文件只保存数据记录的地址。中,表数据文件本身就是一个B+Tree组织的索引结构,这棵树的叶子节点数据域保存了完整的数据记录。该索引的键是数据表的主键,因此表数据文件本身就是主索引。
上图是主索引(也是数据文件)的示意图。可以看到叶子节点包含了完整的数据记录。这种索引称为聚集索引。因为数据文件本身必须通过主键聚合,所以表必须有主键(也可能没有)。如果没有明确指定,MySQL系统会自动选择一个能够唯一标识数据记录的列作为主键。如果不存在这样的列,MySQL会自动生成一个隐式字段作为表的主键。该字段长度为6字节,类型为long。
与索引的第二个区别是,辅助索引的数据字段存储的是相应记录主键的值,而不是地址。换句话说,所有二级索引都引用主键作为数据字段。例如,下图显示了在 Col3 上定义的辅助索引:
这里以英文字符的ASCII码作为比较标准。聚集索引的实现使得主键搜索非常高效,但是辅助索引搜索需要检索索引两次:首先检索辅助索引获取主键,然后使用主键检索主键中的记录指数。
了解不同存储引擎的索引实现对于索引的正确使用和优化非常有帮助。例如,了解了索引的实现之后,就很容易理解为什么不建议使用过长的字段作为主键,因为所有二级索引都引用主索引。 ,主索引太长会使辅助索引太大。再比如,在数据库中使用非单调字段作为主键并不是一个好主意,因为数据文件本身就是一棵B+Tree。非单调主键会导致数据文件在插入新记录时为了保持B+Tree的特性而频繁更新。拆分调整效率很低,使用自增字段作为主键是一个不错的选择。
6. 索引使用策略及优化
MySQL优化主要分为结构优化()和查询优化(Query)。本章讨论的高性能索引策略主要属于结构优化的范畴。本章的内容完全建立在上述理论基础之上。事实上,一旦理解了索引背后的机制,选择高性能策略就变成了纯粹的推理,你就能理解这些策略背后的逻辑。
6.1 联合索引和最左前缀原则
联合索引(复合索引)
首先介绍一下联合索引。联合索引其实很简单。与只有一个字段的普通索引相比,联合索引可以为多个字段创建索引。它的原理也很简单。例如,如果我们在(a,b,c)字段上创建联合索引,则索引记录将首先按A字段排序,然后按B字段排序,最后按C字段排序。因此,联合指数的特点是:
|一个 |乙| C |
| 1 | 2 | 3 |
| 1 | 4 | 2 |
| 1 | 1 | 4 |
| 2 | 3 | 5 |
| 2 | 4 | 4 |
| 2 | 4 | 6 |
| 2 | 5 | 5 |
事实上,联合索引中的查找与字典中的查找是一样的。首先根据第一个字母搜索,然后根据第二个字母搜索,或者只根据第一个字母搜索,但不能跳过第一个字母从第二个字母开始。开始查找字母。这就是所谓的最左前缀原则。
最左前缀原则
下面详细介绍一下联合索引的查询。仍然使用上面的例子,我们在(a,b,c)字段上建立了联合索引,所以这个索引是按照a,然后b,然后c排序的,所以:
以下查询方法可以使用索引
select * from table where a=1;
select * from table where a=1 and b=2;
select * from table where a=1 and b=2 and c=3;
以上三个查询都可以按照(a),(a,b),(a,b,c)的顺序使用索引,即最左边的前缀匹配。
如果查询语句是:
select * from table where a=1 and c=3; 那么只会用到索引a。
如果查询语句是:
select * from table where b=2 and c=3; 因为没有用到最左前缀a,所以这个查询是用户到索引的。
如果使用最左边的前缀,但是顺序颠倒了,会使用索引码吗?
例如:
select * from table where b=2 and a=1;
select * from table where b=2 and a=1 and c=3;
如果使用最左边的前缀但顺序正好相反,也可以使用索引,因为MySQL查询优化器会判断最有效的顺序来纠正这条SQL语句,最终生成真正的执行计划。但我们最好按索引顺序查询,这样查询优化器就不必重新编译。
前缀索引
除了联合索引之外,mysql其实还有一个前缀索引。前缀索引使用列的前缀而不是整个列作为索引键。当前缀长度合适时,不仅可以使前缀索引的选择性接近全列索引,而且还可以因为索引键变短而减少索引文件的大小和维护。开销。
一般来说,前缀索引可以用在以下几种情况:
有的文章还提到:
MySQL前缀索引可以有效减少索引文件的大小,提高索引的速度。但前缀索引也有其缺点:MySQL不能在ORDER BY或GROUP BY中使用前缀索引,也不能用作覆盖索引(Index)。
6.2 索引优化策略
* '%' -- 转到索引
*“%%”——无索引
字符串和数字比较不使用索引;
(阿查尔(10));
*="1" – 转到索引
* FROM a WHERE a=1 – 无索引
正则表达式不使用索引,这应该很容易理解,那么为什么在SQL中很难看到关键字呢
公众号后台回复“微信”关键词,微信添加群主即可免费加入高达商建筑之路微信群,设为星星,并备注建筑之路(公众号主不是需要加入!)
好文章推荐
愚人节快乐!
扫一扫在手机端查看
我们凭借多年的网站建设经验,坚持以“帮助中小企业实现网络营销化”为宗旨,累计为4000多家客户提供品质建站服务,得到了客户的一致好评。如果您有网站建设、网站改版、域名注册、主机空间、手机网站建设、网站备案等方面的需求,请立即点击咨询我们或拨打咨询热线: 13761152229,我们会详细为你一一解答你心中的疑难。