精华内容
下载资源
问答
  • 索引的底层实现原理

    千次阅读 2017-05-26 17:03:44
    对数据库索引的关注从未淡出我的们的讨论,那么数据库索引是什么样的?聚集索引与非聚集索引有什么不同?希望本文对各位同仁有一定的帮助。有不少存疑的地方,诚心希望各位不吝赐教指正,共同进步。[最近首页之争...

    一、引言

    对数据库索引的关注从未淡出我的们的讨论,那么数据库索引是什么样的?聚集索引与非聚集索引有什么不同?希望本文对各位同仁有一定的帮助。有不少存疑的地方,诚心希望各位不吝赐教指正,共同进步。[最近首页之争沸沸扬扬,也不知道这个放在这合适么,苦劳?功劳?……]

     

     

    二、B-Tree

    我们常见的数据库系统,其索引使用的数据结构多是B-Tree或者B+Tree。例如,MsSql使用的是B+Tree,Oracle及Sysbase使用的是B-Tree。所以在最开始,简单地介绍一下B-Tree。

     

    B-Tree不同于Binary Tree(二叉树,最多有两个子树),一棵M阶的B-Tree满足以下条件:
    1)每个结点至多有M个孩子;
    2)除根结点和叶结点外,其它每个结点至少有M/2个孩子;
    3)根结点至少有两个孩子(除非该树仅包含一个结点);
    4)所有叶结点在同一层,叶结点不包含任何关键字信息;
    5)有K个关键字的非叶结点恰好包含K+1个孩子;

    另外,对于一个结点,其内部的关键字是从小到大排序的。以下是B-Tree(M=4)的样例:

      

    对于每个结点,主要包含一个关键字数组Key[],一个指针数组(指向儿子)Son[]。在B-Tree内,查找的流程是:使用顺序查找(数组长度较短时)或折半查找方法查找Key[]数组,若找到关键字K,则返回该结点的地址及K在Key[]中的位置;否则,可确定K在某个Key[i]和Key[i+1]之间,则从Son[i]所指的子结点继续查找,直到在某结点中查找成功;或直至找到叶结点且叶结点中的查找仍不成功时,查找过程失败。

    接着,我们使用以下图片演示如何生成B-Tree(M=4,依次插入1~6):
    从图可见,当我们插入关键字4时,由于原结点已经满了,故进行分裂,基本按一半的原则进行分裂,然后取出中间的关键字2,升级(这里是成为根结点)。其它的依类推,就是这样一个大概的过程。

      

     

    三、数据库索引

    1.什么是索引

    在数据库中,索引的含义与日常意义上的“索引”一词并无多大区别(想想小时候查字典),它是用于提高数据库表数据访问速度的数据库对象。
    A)索引可以避免全表扫描。多数查询可以仅扫描少量索引页及数据页,而不是遍历所有数据页。
    B)对于非聚集索引,有些查询甚至可以不访问数据页。
    C)聚集索引可以避免数据插入操作集中于表的最后一个数据页。
    D)一些情况下,索引还可用于避免排序操作。

     

    当然,众所周知,虽然索引可以提高查询速度,但是它们也会导致数据库系统更新数据的性能下降,因为大部分数据更新需要同时更新索引。

     

     

    2.索引的存储

    一条索引记录中包含的基本信息包括:键值(即你定义索引时指定的所有字段的值)+逻辑指针(指向数据页或者另一索引页)。

      

    当你为一张空表创建索引时,数据库系统将为你分配一个索引页,该索引页在你插入数据前一直是空的。此页此时既是根结点,也是叶结点。每当你往表中插入一行数据,数据库系统即向此根结点中插入一行索引记录。当根结点满时,数据库系统大抵按以下步骤进行分裂:
    A)创建两个儿子结点
    B)将原根结点中的数据近似地拆成两半,分别写入新的两个儿子结点
    C)根结点中加上指向两个儿子结点的指针

     

    通常状况下,由于索引记录仅包含索引字段值(以及4-9字节的指针),索引实体比真实的数据行要小许多,索引页相较数据页来说要密集许多。一个索引页可以存储数量更多的索引记录,这意味着在索引中查找时在I/O上占很大的优势,理解这一点有助于从本质上了解使用索引的优势。

     

     

    3.索引的类型

    A)聚集索引,表数据按照索引的顺序来存储的。对于聚集索引,叶子结点即存储了真实的数据行,不再有另外单独的数据页。
    B)非聚集索引,表数据存储顺序与索引顺序无关。对于非聚集索引,叶结点包含索引字段值及指向数据页数据行的逻辑指针,该层紧邻数据页,其行数量与数据表行数据量一致。

     

    在一张表上只能创建一个聚集索引,因为真实数据的物理顺序只可能是一种。如果一张表没有聚集索引,那么它被称为“堆集”(Heap)。这样的表中的数据行没有特定的顺序,所有的新行将被添加的表的末尾位置。

     

     

    4.聚集索引

    在聚集索引中,叶结点也即数据结点,所有数据行的存储顺序与索引的存储顺序一致。

      

    1)聚集索引与查询操作

    如上图,我们在名字字段上建立聚集索引,当需要在根据此字段查找特定的记录时,数据库系统会根据特定的系统表查找的此索引的根,然后根据指针查找下一个,直到找到。例如我们要查询“Green”,由于它介于[Bennet,Karsen],据此我们找到了索引页1007,在该页中“Green”介于[Greane, Hunter]间,据此我们找到叶结点1133(也即数据结点),并最终在此页中找以了目标数据行。

     

    此次查询的IO包括3个索引页的查询(其中最后一次实际上是在数据页中查询)。这里的查找可能是从磁盘读取(Physical Read)或是从缓存中读取(Logical Read),如果此表访问频率较高,那么索引树中较高层的索引很可能在缓存中被找到。所以真正的IO可能小于上面的情况。

     

     

    2)聚集索引与插入操作

    最简单的情况下,插入操作根据索引找到对应的数据页,然后通过挪动已有的记录为新数据腾出空间,最后插入数据。

     

    如果数据页已满,则需要拆分数据页(页拆分是一种耗费资源的操作,一般数据库系统中会有相应的机制要尽量减少页拆分的次数,通常是通过为每页预留空间来实现):
    A)在该使用的数据段(extent)上分配新的数据页,如果数据段已满,则需要分配新段。
    B)调整索引指针,这需要将相应的索引页读入内存并加锁。
    C)大约有一半的数据行被归入新的数据页中。
    D)如果表还有非聚集索引,则需要更新这些索引指向新的数据页。

     

    特殊情况:
    A)如果新插入的一条记录包含很大的数据,可能会分配两个新数据页,其中之一用来存储新记录,另一存储从原页中拆分出来的数据。
    B)通常数据库系统中会将重复的数据记录存储于相同的页中。
    C)类似于自增列为聚集索引的,数据库系统可能并不拆分数据页,页只是简单的新添数据页。

     

     

    3)聚集索引与删除操作

    删除行将导致其下方的数据行向上移动以填充删除记录造成的空白。

    如果删除的行是该数据页中的最后一行,那么该数据页将被回收,相应的索引页中的记录将被删除。如果回收的数据页位于跟该表的其它数据页相同的段上,那么它可能在随后的时间内被利用。如果该数据页是该段的唯一一个数据页,则该段也被回收。

     

    对于数据的删除操作,可能导致索引页中仅有一条记录,这时,该记录可能会被移至邻近的索引页中,原索引页将被回收,即所谓的“索引合并”。

     

     

    5.非聚集索引

    非聚集索引与聚集索引相比:
    A)叶子结点并非数据结点
    B)叶子结点为每一真正的数据行存储一个“键-指针”对
    C)叶子结点中还存储了一个指针偏移量,根据页指针及指针偏移量可以定位到具体的数据行。
    D)类似的,在除叶结点外的其它索引结点,存储的也是类似的内容,只不过它是指向下一级的索引页的。

     

    聚集索引是一种稀疏索引,数据页上一级的索引页存储的是页指针,而不是行指针。而对于非聚集索引,则是密集索引,在数据页的上一级索引页它为每一个数据行存储一条索引记录。

     

    对于根与中间级的索引记录,它的结构包括:
    A)索引字段值
    B)RowId(即对应数据页的页指针+指针偏移量)。在高层的索引页中包含RowId是为了当索引允许重复值时,当更改数据时精确定位数据行。
    C)下一级索引页的指针

     

    对于叶子层的索引对象,它的结构包括:
    A)索引字段值
    B)RowId

      

    1)非聚集索引与查询操作

    针对上图,如果我们同样查找“Green”,那么一次查询操作将包含以下IO:3个索引页的读取+1个数据页的读取。同样,由于缓存的关系,真实的IO实际可能要小于上面列出的。

     

     

    2)非聚集索引与插入操作

    如果一张表包含一个非聚集索引但没有聚集索引,则新的数据将被插入到最末一个数据页中,然后非聚集索引将被更新。如果也包含聚集索引,该聚集索引将被用于查找新行将要处于什么位置,随后,聚集索引、以及非聚集索引将被更新。

     

     

    3)非聚集索引与删除操作

    如果在删除命令的Where子句中包含的列上,建有非聚集索引,那么该非聚集索引将被用于查找数据行的位置,数据删除之后,位于索引叶子上的对应记录也将被删除。如果该表上有其它非聚集索引,则它们叶子结点上的相应数据也要删除。

     

    如果删除的数据是该数所页中的唯一一条,则该页也被回收,同时需要更新各个索引树上的指针。

     

    由于没有自动的合并功能,如果应用程序中有频繁的随机删除操作,最后可能导致表包含多个数据页,但每个页中只有少量数据。

     

     

    6.索引覆盖

    索引覆盖是这样一种索引策略:当某一查询中包含的所需字段皆包含于一个索引中,此时索引将大大提高查询性能。

     

    包含多个字段的索引,称为复合索引。索引最多可以包含31个字段,索引记录最大长度为600B。如果你在若干个字段上创建了一个复合的非聚集索引,且你的查询中所需Select字段及Where,Order By,Group By,Having子句中所涉及的字段都包含在索引中,则只搜索索引页即可满足查询,而不需要访问数据页。由于非聚集索引的叶结点包含所有数据行中的索引列值,使用这些结点即可返回真正的数据,这种情况称之为“索引覆盖”。

     

    在索引覆盖的情况下,包含两种索引扫描:
    A)匹配索引扫描
    B)非匹配索引扫描

     

     

    1)匹配索引扫描

    此类索引扫描可以让我们省去访问数据页的步骤,当查询仅返回一行数据时,性能提高是有限的,但在范围查询的情况下,性能提高将随结果集数量的增长而增长。

     

    针对此类扫描,索引必须包含查询中涉及的的所有字段,另外,还需要满足:Where子句中包含索引中的“引导列”(Leading Column),例如一个复合索引包含A,B,C,D四列,则A为“引导列”。如果Where子句中所包含列是BCD或者BD等情况,则只能使用非匹配索引扫描。

     

     

    2)非配置索引扫描

    正如上述,如果Where子句中不包含索引的导引列,那么将使用非配置索引扫描。这最终导致扫描索引树上的所有叶子结点,当然,它的性能通常仍强于扫描所有的数据页。

     

     

    [参考]
    [1]http://manuals.sybase.com/onlinebooks/group-asarc/asg1200e/aseperf/@Generic__BookTextView/3358
    [2] http://publib.boulder.ibm.com/infocenter/idshelp/v10/index.jsp?topic=/com.ibm.adref.doc/adref235.htm

    展开全文
  • MySQL索引的底层实现原理一、前言二、索引类型1、Hash索引2、BTree索引和B+Tree索引(1)BTree索引(2)B+Tree索引(3)B+Tree对比BTree有点:3、全文索引 一、前言 MySQL支持诸多存储引擎,而各种存储引擎对索引的...

    一、前言

    MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各有不同,因此MySQL数据库支持多种索引类型,如BTree索引,B+Tree索引,Hash索引,全文索引等等。

    二、索引类型

    1、Hash索引

    只有memory(内存)存储引擎支持Hash索引,Hash索引引用索引列的值计算该值的hashCode,然后在hashCode相应的位置存储该值所在行数据的物理位置,因为使用散列算法,因此访问速度非常快,但是一个值只能对应一个hashCode,而且是散列的分布式,因此Hash索引不支持范围查找和排序的功能。

    2、BTree索引和B+Tree索引

    (1)BTree索引

    BTree索引是平衡搜索多叉树木,如果设树的深度为2d(d > 1),高度为h,那么BTree要满足以下条件:
    ①每个叶子结点的高度要一样,等于h;
    ②每个叶子节点由n-1个key和n个指针point组成,其中d <= n <= 2d,key和point相互间隔,结点两端一定是key;
    ③叶子结点指针都为null;
    ④非叶子结点的key都是[key, data]二元组,其中key表示作为索引的键,data为键值所在行的数据。

    (2)B+Tree索引

    B+Tree是BTree的一个变种,如果设d为树的度,h为数的高度,B+Tree和BTree的不同主要在于:
    ①B+Tree中的非叶子结点不存储数据,只存储键值;
    ②B+Tree的叶子结点没有指针,所有键值都会出现在叶子结点上,且key存储的键值对应data数据的物理地址;
    ③B+Tree的每个非叶子结点由n个键值key和n个指针point组成。

    (3)B+Tree对比BTree优点:

    ①磁盘读写代价更低;
    ②查询速度更稳定。

    3、全文索引

    FullText(全文)索引,仅可用于MyISAM和InnoDB,针对较大的数据,生成全文索引非常的消耗时间和空间。
    在生成FullText索引时,会为文本生成一份单词的清单,在索引时会根据这个单词的清单进行索引。

    展开全文
  • 1 索引的本质 索引(Index)是帮助MySQL高效获取数据的数据结构,为什么需要需要特定的数据结构呢?首先,顺序查找这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,更优秀的查找算法,比如二分查找(binary ...

    1 索引的本质

    索引(Index)是帮助MySQL高效获取数据的数据结构,为什么需要需要特定的数据结构呢?首先,顺序查找这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,更优秀的查找算法,比如二分查找(binary search)、二叉树查找(binary tree search),我们会发现每种查找算法都只能应用于特定的数据结构之上,但是数据本身的组织结构不可能完全满足各种数据结构,所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。

    2 B树

    目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构, B 树可以看作是对2-3查找树的一种扩展, 他允许一个节点有多于2个的元素。

    2.1 特征

    2.1.1 树的阶(至多子树数目)

    树中每个结点至多有m 棵子树 (注:m指的是树的阶)。

    2.1.2 根节点(至少子树数目)

    若根结点不是叶子结点,则至少有两棵子树(注:根节点至少有两个儿子)

    2.1.3 非叶子节点(至少子树数目)

    除根结点之外的所有非叶子结点至少有m/2(向上取整)个子节点

    2.1.4 叶子节点(同层)

    所有的叶子节点都在同一层,并且不带信息

    2.1.5 非叶子结点结构

    关键码即真实数据,所有的非叶子结点中包含以下数据:(n,A0,K1,A1,K2,…,Kn,An),其中,n 为关键码的个数,Ki(i=1,2,…,n)为关键码,且Ki<Ki+1,即从左至右升序排列,Ai 为指向儿子的指针(i=0,1,…,n),且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n),An 所指子树中所有结点的关键码均大于Kn,即每个ki数据两旁各安放了一个指针,即Ai-1和Ai,左边的子树数据统统小于ki,右边子树的数据统统大于ki。

    2.2 渐进复杂度和查找效率

    例如一个度为d的B-Tree,设其索引N个key,则其树高h的上限为logd((N+1)/2),即查找节点个数的渐进复杂度为O(logdN)。从这点可以看出,B-Tree是一个非常有效率的索引数据结构。由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

    3 B+树

    B-Tree有许多变种,其中最常见的是B+Tree,例如MySQL就普遍使用B+Tree实现其索引结构。

    3.1 不同点

    与B-Tree相比,B+Tree有以下不同点:

    关键字+1

    有n棵子树的节点含有n个关键字。

    非叶子节点(关键字和指针)

    它把数据都存储在叶子节点,内部只存关键字(其中叶子节点的最小值作为索引)和孩子指针, 仅具有索引作用,简化了内部节点。

    叶子节点(所有关键字信息,数据和链表)

    所有叶子结点包含所有关键字信息和指向关键字记录的指针,将所以叶子节点串联成链表即可从头到尾遍历。

    核心不同点总结

    B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

    3.2 优势

    B+树的磁盘读写代价更低

    由于B+树在内部节点上不包含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。

    B+树的查询更加稳定

    所有的关键字查询都会走一条从根节点到叶子结点的路径。即s所有关键字查询的长度是一样的,查询效率稳定。

    B+树便于遍历和区间查找

    B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。

    4 MySQL索引实现

    在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式

    4.1 MyISAM( B+Tree,非聚集)

    索引文件仅仅保存数据记录的地址, 主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复

    4.2 InnoDB(B+Tree,聚集索引)

    数据文件本身就是索引文件,叶节点data域保存了完整的数据记录,这个索引的key是数据表的主键。

    4.2.1 InnoDB要求表必须有主键(主索引)

    如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键。

    隐含字段:如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整型。

    4.2.2 辅助索引

    InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。

    4.2.3 扩展

    为什么不建议使用过长的字段作为主键:因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。

    非单调的字段作为主键在不是个好主意:因为InnoDB数据文件本身是一棵B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效。分布式问题,使用自增字段作为主键则是一个很好的选择。

    5 Hash索引

    Hash索引会将计算出的Hash值和对应的行指针信息记录在Hash表中。

    5.1 检索效率非常高

    不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引。

    5.2 弊端和限制

    不能使用范围查询

    Hash 索引仅仅能满足"=",“IN"和”<=>"查询,不能使用范围查询。

    排序操作

    Hash 索引无法被用来避免数据的排序操作。

    组合索引

    Hash 索引不能利用部分索引键(组合索引)查询。

    不能避免表扫描哈希冲突

    Hash 索引在任何时候都不能避免表扫描(哈希冲突需要和数据记录比较)。

    哈希冲突

    Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

    5.3 支持情况(InnoDB)

    InnDB存储引擎支持得哈希索引是自适应的,会根据表得#使用情况自动为表生成哈希索引,不能人为干预是否在一张表中生成哈希索引。

    然后MEMORY存储引擎是基于哈希的,数据都存放于内存,适用于临时表。

    6 索引使用策略及优化

    6.1 使用联合索引

    建一个联合索引(a,b,c),实际相当于建了(a)、(a,b)、(a,b,c)三个索引,所以尽量的扩展索引而不是新增,比如表中已经有a的索引,现在要加(a,b)的索引,那么只需要修改原来的索引即可

    6.1.1 好处

    减少分别建立索引的开销;方便实现覆盖索引;避免单值索引的回表操作(一个索引查询到结果后再回表应用另一个索引),进一步提高效率

    6.1.2 缺点和建议

    相比单值索引占用更多的磁盘空间,降低增删改查的效率,因此单表尽可能不要超过一个联合索引,单个联合索引不超过3个字段。

    6.1.3 最左前缀匹配原则

    最左优先,即以最左边的为起点任何连续的索引都能匹配上。同时遇到范围查询(>、<、between、like)就会停止匹配。

    连续使用索引

    联合索引当然还是一颗B+树,只是健值数量不是一个,而是多个(a,b,c)并按顺序排列(类似order by a,b,c)

    遇范围查询失效

    a值相等的情况下,b值又是按顺序排列的,但a范围查询时b值是无序的,所以遇上范围查询就会停止,剩下的字段都无法使用索引

    mysql查询优化器(自动调整顺序)

    sql语句中字段的顺序不需要和联合索引中定义的字段顺序一致,查询优化器会自己调整顺序

    非左匹配是否能够触发索引

    只要是索引,或某个联合索引的一部分,mysql都可能会采用index类型的方式扫描,所以非左匹配也会触发索引,但不是平时说的那种快速取出。

    ref类型表示mysql会根据特定的算法快速查找到某个符合条件的索引而不是会对索引中每一个数据都进行扫描判断,从而快速取出数据。

    6.2 建议加索引的关键字

    对 where,on,group by,order by 中出现的列使用索引

    6.3 区分度问题

    尽量选择区分度高的列作为索引,区分度的公式是co#unt(distinct col)/count(*),表示字段不重复的比例。

    6.4 数据列大小问题

    对较小的数据列使用索引,这样会使索引文件更小;同时内存中也可以装载更多的索引键,较长的字符串可以考虑使用前缀索引,如;

    前缀索引

    索引的选择性是指不重复的索引值(也称为基数,cardinality)和数据表的记录总数的比值,范围从1/#T到1之间,索引的选择性越高则查询效率越高。

    计算选择性:select 1.0count(distinct left(name,3))/count() from test,分别截取name字符的前几个字母,最后选取的计算值要接近整个取整个name时得出的计算值,然后再选中占用空间小的
    创建前缀索引: alter table city_demo add key (city(6));

    6.5 避免操作索引列

    索引列不能参与计算,保持列“干净”,计算(!=或<>,null 值判断)、函数、类型转换(自动or手动,比如字符串与数字比较不使用索引),会导致索引失效而转向全表扫描

    6.6 注意索引数量

    不要过多创建索引, 权衡索引个数与DML之间关系,DML也就是插入、删除数据操作。因为我们修改表数据时,索引也需要进行调整重建,建议6个以下.

    6.7 like

    对于like查询,”%”不要放在前面。

    展开全文
  • 理解MySQL索引的底层实现原理

    千次阅读 2019-05-21 00:17:36
    理解索引的特性 、索引的本质 、其他结构的问题 、B-Tree 和 B+Tree 、MySQL索引实现


    理解索引的特性

    • 索引是帮助MySQL高效获取数据的排好序的数据结构
    • 索引存储在文件里

    MySQL支持多种索引类型,如BTree索引哈希索引全文索引等等。

    本文主要讨论BTree索引,这也是我们平时用得最多的索引。


    索引的本质

    MySQL官方对于索引的定义为:索引是帮助MySQL高效获取数据的数据结构。 即可以理解为:索引是数据结构

    我们知道,数据库查询是数据库最主要的功能之一,我们都希望查询数据的速度尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找,当然这种时间复杂度为O(n)的算法在数据量很大时显然是糟糕的,于是有了二分查找、二叉树查找等。

    但是二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树,但是数据本身的组织结构不可能完全满足各种数据结构。所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引

    接下来看一个示例:

    上图展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(logn2)O(log2n)的复杂度内获取到相应数据。

    虽然这是一个货真价实的索引,但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black tree)实现的,原因会在下文介绍。

    本文将只关注于BTree索引,因为这是平常使用MySQL时主要使用到的索引。


    其他结构的问题

    由于索引无法装入内存,则必然依赖磁盘(或SSD)存储。而内存的读写速度是磁盘的成千上万倍(与具体实现有关),因此,核心问题是“如何减少磁盘读写次数”。
    首先不考虑页表机制,假设每次读、写都直接穿透到磁盘,那么:

    • 线性结构:读/写平均O(n)次
    • 二叉搜索树(BST):读/写平均O(log2(n))次;如果树不平衡,则最差读/写O(n)次
    • 自平衡二叉搜索树(AVL):在BST的基础上加入了自平衡算法,读/写最大O(log2(n))次
    • 红黑树(RBT):另一种自平衡的查找树,读/写最大O(log2(n))次

    BST、AVL、RBT很好的将读写次数从O(n)优化到O(log2(n));其中,AVL和RBT都比BST多了自平衡的功能,将读写次数降到最大O(log2(n))。

    假设使用自增主键,则主键本身是有序的,树结构的读写次数能够优化到树高树高越低读写次数越少;自平衡保证了树结构的稳定。如果想进一步优化,可以引入B树和B+树。

    在介绍B树之前,先来看另一棵神奇的树——二叉排序树(Binary Sort Tree),首先它是一棵树,“二叉”这个描述已经很明显了,就是树上的一根树枝开两个叉,于是递归下来就是二叉树了(下图所示),而这棵树上的节点是已经排好序的,具体的排序规则如下:

    • 若左子树不空,则左子树上所有节点的值均小于它的根节点的值
    • 若右子树不空,则右字数上所有节点的值均大于它的根节点的值
    • 它的左、右子树也分别为二叉排序树(递归定义)

    从图中可以看出,二叉排序树组织数据时,用于查找是比较方便的,因为每次经过一次节点时,最多可以减少一半的可能,不过极端情况会出现所有节点都位于同一侧,直观上看就是一条直线,那么这种查询的效率就比较低了,因此需要对二叉树左右子树的高度进行平衡化处理,于是就有了平衡二叉树(Balenced Binary Tree)

    所谓“平衡”,说的是这棵树的各个分支的高度是均匀的,它的左子树和右子树的高度之差绝对值小于1,这样就不会出现一条支路特别长的情况。于是,在这样的平衡树中进行查找时,总共比较节点的次数不超过树的高度,这就确保了查询的效率(时间复杂度为O(logn))。

    参考:https://blog.csdn.net/chuixue24/article/details/86594069


    B-Tree 和 B+Tree

    目前大部分数据库系统及文件系统都采用 B-Tree 和 B+Tree 作为索引结构。

    MySQL InnoDB存储引擎是基于B-树(但实际上MySQL采用的是B+树结构)的索引结构。

    注意B-Tree 中文称为 B树没有所谓的B减树,特别是与B+树一起讲的时候。想当然的认为有B+(加)树就有B-(减)树,实际上B+树的英文名是“B+ -Tree”。

    B-树是一种m阶平衡树,叶子节点都在同一层,由于每一个节点存储的数据量比较大,索引整个B-树的层数是非常低的,基本上不超过三层。

    由于磁盘的读取也是按block块操作的(内存是按page页面操作的),因此B-树的节点大小一般设置为和磁盘块大小一致,这样一个B-树节点,就可以通过一次磁盘I/O把一个磁盘块的数据全部存储下来,所以当使用B-树存储索引的时候,磁盘I/O的操作次数是最少的(MySQL的读写效率,主要集中在磁盘I/O上)。

    那么MySQL最终为什么要采用B+树存储索引结构呢,那么看看B-树和B+树在存储结构上有什么不同?

    • B-树的每一个节点,存了关键字和对应的数据地址,而B+树的非叶子节点只存关键字,不存数据地址。因此B+树的每一个非叶子节点存储的关键字是远远多于B-树的,B+树的叶子节点存放关键字和数据,因此,从树的高度上来说,B+树的高度要小于B-树,使用的磁盘I/O次数少,因此查询会更快一些
    • B-树由于每个节点都存储关键字和数据,因此离根节点进的数据,查询的就快,离根节点远的数据,查询的就慢;B+树所有的数据都存在叶子节点上,因此在B+树上搜索关键字,找到对应数据的时间是比较平均的,没有快慢之分
    • 在B-树上如果做区间查找,遍历的节点是非常多的;B+树所有叶子节点被连接成了有序链表结构,因此做整表遍历和区间查找是非常容易的

    B-树的结构图如下:

    B+树的结构图如下:


    MySQL索引实现

    在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,接下来我们主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。


    MyISAM索引实现

    MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

    这里设表一共有三列,假设我们以Col1为主键,则图8是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

    同样也是一颗B+Tree,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的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择

    下篇博文我们将具体讨论这些与索引有关的使用和优化策略。
    在这里插入图片描述

    展开全文
  • 重点讨论BTree(后面涉及到的BTree都是指B+Tree)索引的实现原理。 MySQL的官方定义:索引(index)是帮助MySQL高效获取数据的数据结构,也就是说索引本质上是数据结构。而我们最常用的是使用BTree数据结构作为索引...
  • 1.)索引的分类  索引分为单列索引和多列索引,主键约束自带主键索引,唯一约束自带唯一索引。 2.)索引的创建  2.1)单列索引的创建  create index 索引名 on 表名(列名);  例如:create index emp_inde...
  • MySQL索引底层实现原理 编辑推荐: 本文来自于www.cnblogs.com,了解MySQL索引底层实现原理吗?主要介绍了索引的本质,相关的主存取原理,磁盘原理,局部性原理,带大家了解进行详细的实现。 索引的本质 MySQL...
  • MySQL索引底层实现原理MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。我们知道,数据库查询...
  • 索引底层实现原理

    2020-02-16 23:28:43
    建立索引的原因 索引的选择
  • 如想查询where col2=22的记录,在没有加索引的情况下是按顺序从第一条记录开始查找, 因此需要查找5次才能找到22。 如果对col2列家伙是哪个索引之后, 假设用最简单的二叉树作为索引存储的方式, 再次查找where ...
  • 所以,索引的本质的数据结构。 二、设计原理 为什么要使用索引,很容易想到的目前就是加快查询效率。因此数据库的设计者会从查询算法的角度上开始优化。最基本的查询算法也就是顺序查找,这样的时间复杂度为O(n)的...
  • MySQL索引背后数据结构及算法原理 一、定义 索引定义:索引(Index)是帮助MySQL高效获取数据数据结构。本质:索引是数据结构。 二、B-Tree m阶B-Tree满足以下条件:1、每个节点至多可以拥有m棵子树。2、根...
  • 底层通过B+树实现 优点:可以提高检索数据的速度 缺点:创建和维护需要消耗一定的时间,耗时随数据的增加而增加,需要占用一定的物理空间,增加、删除和修改数据时,需要动态的维护索引 2、索引的分类 2.1普通索引 ...
  • MySQL索引底层实现原理 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。 我们知道,数据库查询是数据库的最主要功能之一。我们都...
  • 当然, 有的数据库也使用哈希桶作用索引的数据结构 , 然而, 主流的RDBMS都是把平衡树当做数据表默认的索引数据结构的。 我们平时建表的时候都会为表加上主键, 在某些关系数据库中, 如果建表时不指定主键,...
  • 删除索引四、索引的执行过程五、索引的底层原理 一、索引的介绍 索引是创建在数据库表中,是对数据库表中的一列或者多列的值进行排序的一种结果,索引是一种提高查询效率的数据结构(B树或者是哈希结构)。 索引...
  • mysql联合索引最左匹配原则的底层实现原理 要看懂,需要熟悉mysql b+ tree的数据结构 b+tree的叶节点和叶子节点的排序特性是按照,从小到大,从左到右的这么一个规则,int直接比大小,uuid比较ASCII码, 联合索引的排序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 754
精华内容 301
关键字:

索引的底层实现原理