迅闻网
让更多人看到你

mysql索引类型(mysql索引实现原理)

  mysql索引类型

索引是数据库存储引擎用于快速查找到指定数据的一种数据结构。
能够用新华字典做类比:假设新华字典中对每个字的具体解说是数据库中表的记载,那么按部首或拼音等排序的目录便是索引,运用它能够让我们快速查找的某一个字具体解说的方位。
在MySQL中,存储引擎也是用了类似的方法,先在索引中找到对应的值,然后再依据匹配的索引值找到对应表中记载的方位。
面试中为什么问索引?
之所以在索引在面试中经常被问到,便是由于:索引是数据库的良好功能表现的关键,也是对查询能优化最有效的手段。索引能够轻易地把查询功能提高几个数量级。
然而,糟糕的索引也同样会影响查询功能,当表中的数据量越来越多的时候,索引对功能的影响就越大。在数据量比较少而且负责比较低的时候,糟糕的索引对功能的影响或许不明显,但是当数据量逐步增多的时候,功能会急剧下降。
索引的类型
通过前面的介绍,我们就进入正题,了解一下MySQL支撑的索引类型,以及它们的原理和用法。
不同类型的索引,可认为不同场景提供更好的功能。在MySQL中,索引是在存储引擎层面完成的,而不是在服务器层面完成的。正如我们所知道,MySQL支撑多种类型的存储引擎。所以,在不同存储引擎中索引的完成方法并不是相同的,也不是一切类型的索引都被一切存储引擎支撑的,即便多个存储引擎支撑同一种类型的索引,它底层的完成也有或许是不相同的。
 B-Tree索引
B-Tree索引是被大多数MySQL存储引擎支撑的,在我们评论索引时,假设没有特别地阐明类型,那么大概率说的便是B-Tree索引了。我们运用B-Tree这个词,是由于MySQL在创立表和其他句子中就运用这个关键字。
然而,在不同存储引擎的底层或许运用不同的数据结构和算法,比方:InnoDB存储引擎内部运用的是B+Tree结构,NDB集群存储引擎内部运用的是T-Tree结构。不同存储引擎用以不同的方法运用B-Tree索引,功能也或许不同,比方:InnoDB的索引上存储的是元数据格式,而MyISAM存储引擎运用前缀压缩技术使索引更小,InnoDB索引的行存储的数据行的主键引证,而MyISAM存储引擎的索引的行存储的是数据行的物理方位。
B-Tree索引的原理
B-Tree索引能够加速访问数据的速度,由于不需要全表扫描就能够快速检索的需要的数据。那么B-Tree索引是怎样做到的呢?我们通过一个简略的比方了解一下InnoDB的B-Tree索引是怎样工作的:
这个表中共有4个字段,分别表明省、市、区和具体地址,还有一个B-Tree索引,其间包含了省、市、区三个字段。由于索引的一切值都是依照次序存储的,即:节点的左子树比当时节点小,节点的右子树比当时节点大。那么当查询数据时,从索引的根节点开始搜索,依据比较当时节点的索引值向子树进行查找,直到找到对应的索引值,或者底子没有找到。

 

mysql
B-Tree索引的用法
依据B-Tree索引的特色,它能够用于全值匹配、值规模匹配和最左前缀匹配。
全值匹配是指和索引中一切的字段进行匹配,比方:查询黑龙江省哈尔滨市南岗区的数据。值规模匹配是指索引中字段的某一规模进行匹配,但是有必要满足前面字段的全匹配,比方:第一个字段province_name省称号的全匹配,第二个字段city_name城市称号的规模匹配。最左前缀匹配是指索引中字段的某一最初部分进行匹配,但是有必要满足前面字段的全匹配,比方:第一个字段province_name省称号为内蒙古,第二个字段city_name城市称号以“呼”最初。哈希索引
哈希索引是根据哈希表完成的,用于精确匹配索引所指向的数据。存储引擎对每一行数据的一切索引字段计算出一个哈希码,哈希码是一个比较小的值,而且不同的数据计算出来的哈希码一般情况下也不相同。哈希索引中存放了这个哈希码和指向这个数据行的指针。
在MySQL中,只要Memory存储引擎支撑哈希索引,也是Memory存储引擎的默认索引类型。别的,在InnoDB存储引擎中也运用了哈希索引,叫做自适应哈希索引。当某些索引中被十分频繁的运用时,InnoDB存储引擎会在内存中根据B-Tree索引之上再创立一个哈希索引,这样一来使得B-Tree索引也具有的快速哈希查找的长处。
哈希索引由于只需存放对应数据的哈希值,所以索引的结构十分紧凑,占用空间小,一起查询速度也十分快。不过,哈希索引只支撑全值等值查询,不能索引字段规模匹配和部分索引字段匹配。
空间数据索引
空间数据索引(R-Tree)主要用于地理数据的存储,会从一切维度来索引数据,查询时能够有效的运用任意维度进行组合查询。 现在,MyISAM存储引擎支撑空间数据索引,不过有必要运用MySQL的GIS相关的函数来保护数据。
在MySQL中,空间索引只能建立在空间数据类型上,如:GEOMETRY、POINT、LINESTRING等。
全文索引
全文索引不像之前介绍的索引那样直接比较索引中的值,而是直接比较查找的文本中的关键词,它类似于搜索引擎做的工作,不是简略的where条件匹配。
在相同的字段上,能够一起创立全文索引和B-Tree索引,不会有冲突。全文索引适用于match和against操作,不是普通的where条件操作。在MySQL中,只能在类型为CHAR、VARCHAR、TEXT的字段上创立全文索引。

mysql索引实现原理

MySQL官方对索引的界说为:索引(Index)是协助MySQL高效获取数据的数据结构。提取语句骨干,就能够得到索引的本质:索引是数据结构。
咱们知道,数据库查询是数据库的最首要功能之一。咱们都期望查询数据的速度能尽或许的快,因而数据库体系的设计者会从查询算法的视点进行优化。最根本的查询算法当然是次序查找(linear search),这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的开展供给了许多更优异的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。假如稍微剖析一下会发现,每种查找算法都只能运用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能运用于二叉查找树上,可是数据自身的安排结构不或许彻底满意各种数据结构(例如,理论上不或许一起将两列都按次序进行安排),所以,在数据之外,数据库体系还维护着满意特定查找算法的数据结构,这些数据结构以某种方法引证(指向)数据,这样就能够在这些数据结构上完成高级查找算法。这种数据结构,便是索引。
看一个例子:
上图展现了一种或许的索引方法。左边是数据表,一共有两列七条记载,最左边的是数据记载的物理地址(注意逻辑上相邻的记载在磁盘上也并不是必定物理相邻的)。为了加速Col2的查找,能够维护一个右边所示的二叉查找树,每个节点别离包含索引键值和一个指向对应数据记载物理地址的指针,这样就能够运用二叉查找在O(logn2)O(log2n)的复杂度内获取到相应数据。
尽管这是一个货真价实的索引,可是实践的数据库体系几乎没有运用二叉查找树或其进化品种红黑树(red-black tree)完成的,原因会在下文介绍。
二叉排序树
在介绍B树之前,先来看另一棵神奇的树——二叉排序树(Binary Sort Tree),首先它是一棵树,“二叉”这个描绘现已很明显了,便是树上的一根树枝开两个叉,于是递归下来便是二叉树了(下图所示),而这棵树上的节点是现已排好序的,详细的排序规矩如下:
若左子树不空,则左子树上一切节点的值均小于它的根节点的值
若右子树不空,则右字数上一切节点的值均大于它的根节点的值
它的左、右子树也别离为二叉排序数(递归界说)
从图中能够看出,二叉排序树安排数据时,用于查找是比较方便的,因为每次经过一次节点时,最多能够减少一半的或许,不过极点状况会呈现一切节点都位于同一侧,直观上看便是一条直线,那么这种查询的功率就比较低了,因而需求对二叉树左右子树的高度进行平衡化处理,于是就有了平衡二叉树(Balenced Binary Tree)。
所谓“平衡”,说的是这棵树的各个分支的高度是均匀的,它的左子树和右子树的高度之差绝对值小于1,这样就不会呈现一条支路特别长的状况。于是,在这样的平衡树中进行查找时,总共比较节点的次数不超越树的高度,这就保证了查询的功率(时刻复杂度为O(logn))
B树
还是直接看图比较清楚,图中所示,B树事实上是一种平衡的多叉查找树,也便是说最多能够开m个叉(m>=2),咱们称之为m阶b树,为了表现本博客的良心之处,不同于其他地方都能看到2阶B树,这儿特意画了一棵5阶B树 。
总的来说,m阶B树满意以下条件:
每个节点至多能够拥有m棵子树。
根节点,只有至少有2个节点(要么极点状况,便是一棵树就一个根节点,单细胞生物,便是根,也是叶,也是树)。
非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表明向上取整,图中5阶B树,每个节点至少有3个子树,也便是至少有3个叉)。
非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An],,其中n表明该节点中保存的关键字个数,K为关键字且Ki
从根到叶子的每一条途径都有相同的长度,也便是说,叶子节在相同的层,而且这些节点不带信息,实践上这些节点就表明找不到指定的值,也便是指向这些节点的指针为空。
B树的查询进程和二叉排序树比较相似,从根节点顺次比较每个结点,因为每个节点中的关键字和左右子树都是有序的,所以只需比较节点中的关键字,或许沿着指针就能很快地找到指定的关键字,假如查找失败,则会回来叶子节点,即空指针。
例如查询图中字母表中的K:
从根节点P开端,K的方位在P之前,进入左侧指针。
左子树中,顺次比较C、F、J、M,发现K在J和M之间。
沿着J和M之间的指针,持续拜访子树,并顺次进行比较,发现第一个关键字K即为指定查找的值。
B树查找的简略伪算法如下:
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树的特色能够总结为如下:
关键字调集散布在整颗树中。
任何一个关键字呈现且只呈现在一个节点中。
查找有或许在非叶子节点结束。
其查找功能等价于在关键字调集内做一次二分查找。
B树在插入删去新的数据记载会损坏B-Tree的性质,因为在插入删去时,需求对树进行一个割裂、合并、转移等操作以坚持B-Tree性质。

mysql
Plus版 — B+树
作为B树的加强版,B+树与B树的差异在于
有n棵子树的节点含有n个关键字(也有认为是n-1个关键字)。
一切的关键字悉数存储在叶子节点上,且叶子节点自身根据关键字自小而大次序连接。
非叶子节点能够看成索引部分,节点中仅含有其子树(根节点)中的最大(或最小)关键字。
B+树的查找进程,与B树相似,只不过查找时,假如在非叶子节点上的关键字等于给定值,并不停止,而是持续沿着指针直到叶子节点方位。因而在B+树,不管查找成功与否,每次查找都是走了一条从根到叶子节点的途径。
B+树的特性如下:
一切关键字都存储在叶子节上,且链表中的关键字恰好是有序的。
不或许非叶子节点射中回来。
非叶子节点相当于叶子节点的索引,叶子节点相当于是存储(关键字)数据的数据层。
更适合文件索引体系。
带有次序拜访指针的B+Tree
一般在数据库体系或文件体系中运用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了次序拜访指针。
如上图所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有次序拜访指针的B+Tree。做这个优化的意图是为了提高区间拜访的功能,例如图4中假如要查询key为从18到49的一切数据记载,当找到18后,只需顺着节点和指针次序遍历就能够一次性拜访到一切数据节点,极大提到了区间查询功率。
MySQL为什么运用B树(B+树)
红黑树等数据结构也能够用来完成索引,可是文件体系以及数据库体系普遍选用B树或许B+树,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。
一般来说,索引自身也很大,不或许悉数存储在内存中,因而索引往往以索引文件的方法存储在磁盘上。这样的话,索引查找进程中就要发生磁盘I/O耗费,相关于内存存取,I/O存取的耗费要高几个数量级,所以点评一个数据结构作为索引的好坏最重要的指标便是在查找进程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构安排要尽量减少查找进程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理剖析B-/+Tree作为索引的功率。
主存存取原理
目前计算机运用的主存根本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这儿本文抛却详细不同,抽象出一个十分简略的存取模型来阐明RAM的工作原理。
从抽象视点看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定巨细的数据。每个存储单元有仅有的地址,现代主存的编址规矩比较复杂,这儿将其简化成一个二维地址:经过一个行地址和一个列地址能够唯必定位到一个存储单元。上图展现了一个4 x 4的主存模型。
主存的存取进程如下:
当体系需求读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。
写主存的进程相似,体系将要写入单元地址和数据别离放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。
这儿能够看出,主存存取的时刻仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“间隔”不会对时刻有任何影响,例如,先取A0再取A1和先取A0再取D3的时刻耗费是相同的。
磁盘存取原理
上文说过,索引一般以文件方法存储在磁盘上,索引检索需求磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因而磁盘I/O的时刻耗费是巨大的。
下图是磁盘的整体结构示意图:
一个磁盘由巨细相同且同轴的圆形盘片组成,磁盘能够滚动(各个磁盘必须同步滚动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能滚动,可是能够沿磁盘半径方向运动(实践是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,一切磁头任何时候都是堆叠的(不过目前现已有多磁头独立技能,可不受此限制)。
下图是磁盘结构的示意图:
盘片被划分红一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,一切半径相同的磁道组成一个柱面。磁道被沿半径线划分红一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简略起见,咱们下面假设磁盘只有一个盘片和一个磁头。
当需求从磁盘读取数据时,体系会将数据逻辑地址传给磁盘,磁盘的控制电路依照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需求将磁头放到这个扇区上方,为了完成这一点,磁头需求移动对准相应磁道,这个进程叫做寻道,所耗费时刻叫做寻道时刻,然后磁盘旋转将目标扇区旋转到磁头下,这个进程耗费的时刻叫做旋转时刻。
局部性原理与磁盘预读
因为存储介质的特性,磁盘自身存取就比主存慢许多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因而为了提高功率,要尽量减少磁盘I/O。为了到达这个意图,磁盘往往不是严格按需读取,而是每次都会预读,即便只需求一个字节,磁盘也会从这个方位开端,次序向后读取必定长度的数据放入内存。这样做的理论依据是计算机科学中闻名的局部性原理:
当一个数据被用到时,其附近的数据也一般会马上被运用。
所以,程序运转期间所需求的数据一般应当比较集中。
因为磁盘次序读取的功率很高(不需求寻道时刻,只需很少的旋转时刻),因而关于具有局部性的程序来说,预读能够提高I/O功率。
预读的长度一般为页(page)的整倍数。页是计算机办理存储器的逻辑块,硬件及操作体系往往将主存和磁盘存储区别割为接连的巨细持平的块,每个存储块称为一页(在许多操作体系中,页得巨细一般为4k),主存和磁盘以页为单位交流数据。当程序要读取的数据不在主存中时,会触发一个缺页反常,此时体系会向磁盘宣布读盘信号,磁盘会找到数据的起始方位并向后接连读取一页或几页载入内存中,然后反常回来,程序持续运转。
B-/+Tree索引的功能剖析
到这儿终于能够剖析B-/+Tree索引的功能了。
上文说过一般运用磁盘I/O次数点评索引结构的好坏。先从B-Tree剖析,根据B-Tree的界说,可知检索一次最多需求拜访h个节点。数据库体系的设计者奇妙运用了磁盘预读原理,将一个节点的巨细设为等于一个页,这样每个节点只需求一次I/O就能够彻底载入。为了到达这个意图,在实践完成B-Tree还需求运用如下技巧:
每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就完成了一个node只需一次I/O。
B-Tree中一次检索最多需求h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)O(h)=O(logdN)。一般实践运用中,出度d是十分大的数字,一般超越100,因而h十分小(一般不超越3)。(h表明树的高度 & 出度d表明的是树的度,即树中各个节点的度的最大值)
综上所述,用B-Tree作为索引结构功率是十分高的。
而红黑树这种结构,h明显要深的多。因为逻辑上很近的节点(父子)物理上或许很远,无法运用局部性,所以红黑树的I/O渐进复杂度也为O(h),功率明显比B-Tree差许多。
上文还说过,B+Tree更适合外存索引,原因和内节点出度d有关。从上面剖析能够看到,d越大索引的功能越好,而出度的上限取决于节点内key和data的巨细:
dmax=floor(pagesize/(keysize+datasize+pointsize))dmax=floor(pagesize/(keysize+datasize+pointsize))
floor表明向下取整。因为B+Tree内节点去掉了data域,因而能够拥有更大的出度,拥有更好的功能。
MySQL索引完成
在MySQL中,索引归于存储引擎级别的概念,不同存储引擎对索引的完成方法是不同的,本文首要讨论MyISAM和InnoDB两个存储引擎的索引完成方法。
MyISAM索引完成
MyISAM引擎运用B+Tree作为索引结构,叶节点的data域寄存的是数据记载的地址。下图是MyISAM索引的原理图:
这儿设表一共有三列,假设咱们以Col1为主键,则上图是一个MyISAM表的主索引(Primary key)示意。能够看出MyISAM的索引文件仅仅保存数据记载的地址。在MyISAM中,主索引和辅佐索引(Secondary key)在结构上没有任何区别,仅仅主索引要求key是仅有的,而辅佐索引的key能够重复。假如咱们在Col2上树立一个辅佐索引,则此索引的结构如下图所示:
同样也是一棵B+树,data域保存数据记载的地址。因而,MyISAM中索引检索的算法为首先依照B+Tree查找算法查找索引,假如指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记载。
MyISAM的索引方法也叫做“非集合”的,之所以这么称号是为了与InnoDB的集合索引区别。
InnoDB索引完成
尽管InnoDB也运用B+Tree作为索引结构,但详细完成方法却与MyISAM天壤之别。
第一个重大区别是InnoDB的数据文件自身便是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记载的地址。而在InnoDB中,表数据文件自身便是按B+Tree安排的一个索引结构,这棵树的叶节点data域保存了完好的数据记载。这个索引的key是数据表的主键,因而InnoDB表数据文件自身便是主索引。
上图是InnoDB主索引(一起也是数据文件)的示意图,能够看到叶节点包含了完好的数据记载。这种索引叫做集合索引。因为InnoDB的数据文件自身要按主键集合,所以InnoDB要求表必须有主键(MyISAM能够没有),假如没有显式指定,则MySQL体系会主动挑选一个能够仅有标识数据记载的列作为主键,假如不存在这种列,则MySQL主动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整型。
第二个与MyISAM索引的不同是InnoDB的辅佐索引data域存储相应记载主键的值而不是地址。换句话说,InnoDB的一切辅佐索引都引证主键作为data域。例如,上图为界说在Col3上的一个辅佐索引:
这儿以英文字符的ASCII码作为比较原则。集合索引这种完成方法使得按主键的查找十分高效,可是辅佐索引查找需求检索两遍索引:首先检索辅佐索引取得主键,然后用主键到主索引中检索取得记载。
了解不同存储引擎的索引完成方法关于正确运用和优化索引都十分有协助,例如知道了InnoDB的索引完成后,就很容易理解为什么不主张运用过长的字段作为主键,因为一切辅佐索引都引证主索引,过长的主索引会令辅佐索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件自身是一棵B+Tree,非单调的主键会造成在插入新记载时数据文件为了维持B+Tree的特性而频频的割裂调整,十分低效,而运用自增字段作为主键则是一个很好的挑选。

未经允许不得转载:迅闻网 » mysql索引类型(mysql索引实现原理)
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

迅闻网-让更多人看到你

登录/注册返回首页