`

【转】MySQL索引工作原理

阅读更多

转载文章,原文地址:http://blog.csdn.net/iefreer/article/details/15815455

 

为什么需要索引(Why is it needed)?

当数据保存在磁盘类存储介质上时,它是作为数据块存放。这些数据块是被当作一个整体来访问的,这样可以保证操作的原子性。硬盘数据块存储结构类似于链表,都包含数据部分,以及一个指向下一个节点(或数据块)的指针,不需要连续存储。

记录集只能在某个关键字段上进行排序,所以如果需要在一个无序字段上进行搜索,就要执行一个线性搜索(Linear Search)的过程,平均需要访问N/2的数据块,N是表所占据的数据块数目。如果这个字段是一个非主键字段(也就是说,不包含唯一的访问入口),那么需要在N个数据块上搜索整个表格空间。

但是对于一个有序字段,可以运用二分查找(Binary Search),这样只要访问log2 (N)的数据块。这就是为什么性能能得到本质上的提高。

 

什么是索引(What is indexing)?

索引是对记录集的多个字段进行排序的方法。在一张表中为一个字段创建一个索引,将创建另外一个数据结构,包含字段数值以及指向相关记录的指针,然后对这个索引结构进行排序,允许在该数据上进行二分法排序。

副作用是索引需要额外的磁盘空间,对于MyISAM引擎而言,这些索引是被统一保存在一张表中的,这个文件将很快到达底层文件系统所能够支持的大小限制,如果很多字段都建立了索引的话。

 

索引如何工作(How does it work?)

首先,我们建立一个示范数据库表:

字段名       数据类型      大小

id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

注意:使用char是为了指定准确的磁盘占用大小。这个示范数据库包含500万行,而且没有索引。我们将分析一些查询语句的性能,一个是使用主键id(有序)查询,一个是使用firstName(非关键无序字段)。

例1
我们的示范数据库有r=5,000,000条记录,每条记录长度R=204字节而且使用MyISAM引擎存储(默认数据块大小为B=1024字节),这张表的块因子(blocking factor)会是bfr = (B/R) = 1024/204 = 5 条记录每磁盘数据块。保存这张表所需要的磁盘块为N = (r/bfr) = 5000000/5 = 1,000,000 blocks。

在id字段上的线性搜索平均需要N/2 = 500,000块访问来找到一条记录假设id字段是查询关键值,不过既然id字段是有序的,可以执行一个二分查询,这样平均只需要访问log2 (1000000) = 19.93 = 20 个数据块。我们马上就看到了极大的提高。

现在firstName字段既不是有序的,无法执行二分搜索,数值也不具有唯一性,所以对这张表的查找必须到最后一个记录即全表扫描N = 1,000,000个数据块访问。这就是索引用来改进的地方。

假如索引记录只包含一个索引列以及一个指向原记录数据的指针,那么它显而易见会比原记录(多列)要小。所以索引本身所需要的磁盘块要更少,扫描数目也少。firstName索引表结构如下:

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes

 注意: MySQL里的指针按表大小的不同分别可能是 2, 3, 4 或 5 个字节。

例2
假设我们的数据库有r = 5,000,000 条记录,建立了一个长R = 54字节的索引,并且使用默认磁盘块大小为1,024字节。那么该索引的块因子为bfr = (B/R) = 1024/54 = 18 条记录每磁盘块。容纳这个索引表总共需要的磁盘块为N = (r/bfr) = 5000000/18 = 277,778 块。

现在使用FirstName字段来进行搜索就可以利用索引来提高性能。这允许使用一个二分查找,平均log2 (277778) = 18.08 -> 19次数据块访问。找到实际记录的地址,这需要进一步的块读取,这样总数达到19 + 1 = 20次数据块访问,这和非索引表的数据块访问次数有天壤之别。

 

什么时候使用索引(When should it be used?)

鉴于创建索引需要额外的磁盘空间(上面的例子需要额外的277778个磁盘块),以及太多的索引会导致文件系统大小限制所产生的问题,所以对哪些字段建立索引,什么情况下使用索引,需要审慎考虑。

由于索引只是用来加速数据查询,那么显然对只是用来输出的字段建立索引会浪费磁盘空间以及发生插入、删除操作时的处理时间,所以这种情况下应该尽量避免。此外鉴于二分搜索的特性,数据的基数或独立性是很重要的。在基数为2的字段上建立索引,将把数据分割一半,而基数为1000则将返回大约1000条记录。低基数的二分查找效率将降低为一个线性排序,而且查询优化器可能会在基数小于记录数某个比例时(如30%)的情况下将避免使用索引而直接查询原表,所以这种情况下的索引浪费了空间。

 

分享到:
评论

相关推荐

    由浅入深探究mysql索引结构原理、性能分析与优化

    由浅入深探究mysql索引结构原理、性能分析与优化

    MySQL Innodb 索引原理详解

    ### MySQL Innodb 索引原理详解 #### 1. 各种树形结构 在深入探讨MySQL Innodb索引之前,我们先了解几种基本的树形数据结构,包括二叉搜索树、B树、B+树以及B*树。 ##### 1.1 搜索二叉树(Binary Search Tree) ...

    Mysql-索引原理分析

    MySQL数据库中的索引是提升查询性能的关键工具,它的工作原理和设计细节对于数据库管理员和开发者来说至关重要。让我们深入探讨一下标题和描述中提及的几个关键概念。 首先,我们来看看索引的存储结构。在MySQL中,...

    MySQL索引背后的数据结构及算法原理

    ### MySQL索引背后的数据结构及算法原理 #### 数据结构及算法基础 索引在数据库中的作用至关重要,它能够显著提高数据检索的速度。正如标题所提到的,“MySQL索引背后的数据结构及算法原理”这一主题是技术面试中...

    MySQL索引原理

    ### MySQL索引原理详解 #### 一、索引的基本概念 **索引**是帮助MySQL高效获取数据的数据结构。在数据库中,索引扮演着极其重要的角色,它能够显著提高数据检索的速度,尤其是在处理大规模数据集时尤为重要。索引...

    MySQL索引原理及慢查询优化1

    MySQL索引原理及慢查询优化是数据库管理中的重要主题,尤其是在高并发、大数据量的互联网环境中,优化查询性能对于系统的整体效能至关重要。MySQL作为广泛使用的开源关系型数据库,其索引机制和查询优化技巧是开发者...

    MySQL索引及其原理1

    在本文中,我们将深入理解MySQL索引的定义、类型、原理以及如何在实践中有效利用它们。 1. **索引定义** 索引是一种数据结构,其目的是帮助MySQL快速获取数据。它使得数据的查找、排序和访问更加高效。在数据库中...

    MySQL 索引最佳实践

    ### MySQL索引最佳实践 #### 理解索引的重要性 在数据库管理中,索引是一种数据结构,用于提高查询速度...通过深入理解不同的索引类型及其工作原理,开发者和DBA能够更好地优化他们的应用程序并避免常见的性能陷阱。

    mysql索引原理深入解析

    MySQL 索引原理深入解析将带领我们理解数据库索引的工作机制,以及它们如何显著提升查询性能。首先,我们来看一下索引的基本概念。 索引是数据库管理系统中的关键组件,它是一个排序的数据结构,用于加速对数据库表...

    【含动画效果】mysql索引原理与最佳实践.pptx

    从数据结构底层实现,阐述B树、B+树的特点,到mysql为什么选择了B+树作为索引存储结构。接着介绍mysql底层存储实现段簇页,和聚簇索引非聚簇索引包括联合索引的关系。最后列举一些sql是否可走索引,涉及最左匹配原则...

    MySQL索引优化课件

    本课件主要聚焦于MySQL数据库的索引原理、优化策略以及相关存储过程和触发器的应用。 首先,我们要理解什么是索引。索引就像书的目录,它为数据库中的数据提供快速访问的途径。在MySQL中,常见的索引类型有B-Tree...

    MySQL索引背后的数据结构及算法原理-07071521.pdf

    综上所述,了解MySQL索引背后的数据结构和算法原理对于数据库性能优化至关重要。数据库工程师通过深入学习这些知识点,不仅可以更加有效地设计数据库和构建索引,还能在实际工作中应对复杂的查询优化问题,从而提高...

    mysql的索引优化

    #### 三、索引的工作原理 - **索引结构**:MySQL索引通常是以B树形式存储的。B树具有良好的查询性能,即使在大型数据集中也能保持高效的查找能力。 - **索引的组成**:对于每个索引项,MySQL都会保存一个指向实际...

    MySQL索引分析和优化.pdf

    ### MySQL索引分析和优化 #### 一、索引的重要性及原理 索引在数据库管理中扮演着极其重要的角色,特别是在提高数据检索速度方面。**MySQL索引**本质上是用来加快数据检索过程的一种数据结构,类似于书籍中的目录...

    掌握Mysql索引底层原理让你轻松涨薪5K

    掌握Mysql索引底层原理让你轻松涨薪5K

    MYSQL索引知识

    MySQL索引知识是数据库管理中至关重要的一部分,它能显著提高数据查询的速度,特别是在处理大量数据时。索引就像书的目录,使得数据检索更为高效。MySQL中的索引主要有两种存储类型:BTREE(B树)和HASH。 1. **...

    Mysql架构、索引介绍及原理分析.zip

    Mysql架构、索引介绍及原理分析.zipMysql架构、索引介绍及原理分析.zipMysql架构、索引介绍及原理分析.zipMysql架构、索引介绍及原理分析.zipMysql架构、索引介绍及原理分析.zipMysql架构、索引介绍及原理分析....

Global site tag (gtag.js) - Google Analytics