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

    千次阅读 多人点赞 2019-01-13 17:18:08
    MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。 我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能...

    1、 索引的本质

    MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

    我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。
    看一个例子:
    在这里插入图片描述
    上图展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2 n)的复杂度内获取到相应数据。

    虽然这是一个货真价实的索引,但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树

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

    • 若左子树不空,则左子树上所有节点的值均小于它的根节点的值
    • 若右子树不空,则右字数上所有节点的值均大于它的根节点的值
    • 它的左、右子树也分别为二叉排序数(递归定义)
      在这里插入图片描述
      从图中可以看出,二叉排序树组织数据时,用于查找是比较方便的,因为每次经过一次节点时,最多可以减少一半的可能,不过极端情况会出现所有节点都位于同一侧,直观上看就是一条直线,那么这种查询的效率就比较低了,因此需要对二叉树左右子树的高度进行平衡化处理,于是就有了平衡二叉树(Balenced Binary Tree)。

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

    B树

    还是直接看图比较清楚,图中所示,B树事实上是一种平衡的多叉查找树,也就是说最多可以开m个叉(m>=2),我们称之为m阶b树
    在这里插入图片描述
    总的来说,m阶B树满足以下条件:

    • 每个节点至多可以拥有m棵子树。
    • 根节点,只有至少有2个节点(要么极端情况,就是一棵树就一个根节点,单细胞生物,即是根,也是叶,也是树)。
    • 非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整,图中5阶B树,每个节点至少有3个子树,也就是至少有3个叉)。
    • 非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An],,其中n表示该节点中保存的关键字个数,K为关键字且Ki<Ki+1,A为指向子树根节点的指针。
    • 从根到叶子的每一条路径都有相同的长度,也就是说,叶子节在相同的层,并且这些节点不带信息,实际上这些节点就表示找不到指定的值,也就是指向这些节点的指针为空。(解释:叶子节点不含有任何信息

    B树的查询过程和二叉排序树比较类似,从根节点依次比较每个结点,因为每个节点中的关键字和左右子树都是有序的,所以只要比较节点中的关键字,或者沿着指针就能很快地找到指定的关键字,如果查找失败,则会返回叶子节点,即空指针。

    例如查询图中字母表中的K:提示:看下面这个例子就很容易理解B树的查询过程)

    从根节点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树的特点可以总结为如下:

    1. 关键字集合分布在整颗树中。
    2. 任何一个关键字出现且只出现在一个节点中。
    3. 搜索有可能在非叶子节点结束。
    4. 其搜索性能等价于在关键字集合内做一次二分查找。
    5. B树在插入删除新的数据记录会破坏B-Tree的性质,因为在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。

    Plus版 — B+树

    作为B树的加强版,B+树与B树的差异在于

    • 有n棵子树的节点含有n个关键字(也有认为是n-1个关键字)。
    • 所有的关键字全部存储在叶子节点上,且叶子节点本身根据关键字自小而大顺序连接。
    • 非叶子节点可以看成索引部分,节点中仅含有其子树(根节点)中的最大(或最小)关键字。
      在这里插入图片描述
      重点: B+树的查找过程,与B树类似,只不过查找时,如果在非叶子节点上的关键字等于给定值,并不终止,而是继续沿着指针直到叶子节点位置。因此在B+树,不管查找成功与否,每次查找都是走了一条从根到叶子节点的路径。(理解核心

    B+树的特性如下:

    • 所有关键字都存储在叶子节上,且链表中的关键字恰好是有序的。
    • 不可能非叶子节点命中返回。
    • 非叶子节点相当于叶子节点的索引,叶子节点相当于是存储(关键字)数据的数据层。
    • 更适合文件索引系统。

    带有顺序访问指针的B+Tree

    解释:说白了就是在叶子节点部分加上顺序指针,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能
    一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针。
    在这里插入图片描述
    例如上图中如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率。

    问题一:MySQL为什么使用B树(B+树)

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储在磁盘上。这样的话,索引查找过程中就要产生磁盘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)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。(h表示树的高度 & 出度d表示的是树的度,即树中各个节点的度的最大值)(因为总结点数不变,h和d肯定是成反比例的

    综上所述,用B-Tree作为索引结构效率是非常高的。

    而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多

    上文还说过,B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小解释:因为页的大小pagesize固定,所以节点内key和data的大小越小,那么一个页就能存储的节点数就多,出度也就越大):

    dmax=floor(pagesize/(keysize+datasize+pointsize))

    floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。

    展开全文
  • 讨论MySQL索引底层实现

    千次阅读 2016-10-02 15:35:35
    MySQL支持多种索引类型,如BTree索引,哈希索引,全文索引等待。 本文主要讨论BTree索引,这也是我们平时用得最多的索引索引的本质 MySQL官方对于索引的定义为:索引是帮助MySQL高效获取数据的数据结构。即...

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


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


    索引的本质

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


    我们知道,数据库查询是数据库最主要的功能之一,我们都希望查询数据的速度尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找,当然这种时间复杂度为O(n)的算法在数据量很大时显然是糟糕的,于是有了二分查找、二叉树查找等。但是二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树,但是数据本身的组织结构不可能完全满足各种数据结构。所以,在数据之外,数据库系统还维护者满足特定查找算法的数据结构,这些数据结构以某种方式引用数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。


    B-Tree和B+Tree

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


    B-Tree

    为了描述B-Tree,首先定义一条数据记录为一个二元组[key,data],key为记录的键值,对于不同的数据记录,Key是不相同的;data为数据记录除key外的数据。B-Tree满足下列条件的数据结构:

    1.d为大于1的正整数,称为B-Tree的度;

    2.h为一个正整数,称为B-Tree的高度;

    3.每个非叶子节点由n-1个key和n个指针组成,其中d<=n<=2d;

    4.每个叶子节点最少包含一个key和两个指针,最多包含2d-1个Key和2d个指针,叶节点的指针均为null;

    5.所有叶节点具有相同的深度,等于树高h;

    6.key和指针相互隔离,节点两端是指针;

    7.一个节点中的key从左到右非递减排列;

    8.所有节点组成树结构;

    9.每个指针要么为null,要么指向另外一个节点;

    10.如果某个指针在节点node最左边且不为null,则其指向节点的所有key小于v(key1),其中v(key1)为node的第一个key的值;

    11.如果某个指针在节点node最右边且不为null,则其指向节点的所有key大于v(keym),其中v(keym)为node的最后一个key的值;

    12.如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null,则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。





    由于B-Tree的特性,在B-Tree中按Key检索数据的算法非常直观:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或找到null指针,前者查找成功,后者查找失败。

    B-Tree上的查找算法如下:

    <span style="font-size:14px;"><span style="font-family:Microsoft YaHei;font-size:14px;"><span style="font-size:14px;">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);</span></span></span>
    由于插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree的性质。


    B+Tree

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

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

    1.每个节点的指针上限为2d而不是2d+1

    2.内节点不存储data,只存储Key;叶子节点不存储指针。



    由于并不是所有节点都具有相同的域,因此B+Tree中叶节点和内节点一般大小不同。这点与B-Tree不同,虽然B-Tree中不同节点存放的key和指针可能数量不一致,但是每个节点的域和上限是一致的,所以实现中B-Tree往往对每个节点申请同等大小的空间

    一般来说,B+Tree比B-Tree更适合实现外存储索引结构。


    带有顺序访问指针的B+Tree

    一般在数据库系统或文件系统中使用B+Tree结构都是在经典的B+Tree的基础上做了优化,增加了顺序访问指针。



    如图所示,在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。这个优化的目的是为了提高区间访问的性能。例如,在图中要查找key为18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点,极大提高了区间查询效率。


    为什么使用B-Tree(B+Tree)

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储在磁盘上。这样的话,索引查找过程就要产生I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。


    主存存取原理

    目前计算机使用的主存基本上都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里抽象出一个十分简单的存取模型来说明RAM的工作原理。



    从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。


    主存读取过程如下:

    当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其他部件读取。

    写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。


    磁盘读取原理

    索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。



    当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区的上方,为了实现这一点,磁头需要移动对准相应的磁道,这个过程叫做寻道,所耗费的时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。


    局部性原理和磁盘预读

    局部性原理:当一个数据被用到时,其附近的数据也通常会马上被使用。

    程序运行期间所需要的数据通常比较集中。

    由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。 

    预读的长度一般为页的整倍数,页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储称为一页(在许多操作系统,页的大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续执行。


    B-/+Tree索引性能的分析

    根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统设计利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的,在实际实现B-Tree还需要如下技巧:

    每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

    B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存),渐进复杂度为O(h)=O(logdN)。


    MyISAM索引实现

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


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


    同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。


    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上的一个辅助索引:



    聚集索引这种实现方式使得按主键的搜索十分高效,但辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到索引中检索获得记录。








                                                                                                                                                                                                 


    展开全文
  • MySQL 索引底层实现原理(B-tree、B+tree)

    千次阅读 2019-10-29 14:21:49
    文章目录理解索引的特性索引的本质其他结构的问题B-Tree 和 B+TreeMySQL索引实现MyISAM索引实现InnoDB索引实现 理解索引的特性 索引是帮助MySQL高效获取数据的排好序的数据结构 索引存储在文件里 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的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择

    下篇博文我们将具体讨论这些与索引有关的使用和优化策略。

    展开全文
  • MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。 我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽...

    大纲

    在这里插入图片描述

    索引的本质

    MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干,就可以得到索引的本质:索引是数据结构。

    我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search),这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

    看一个例子:
    image.png-32.8kB

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

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

    二叉排序树

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

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

    img

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

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

    B树

    还是直接看图比较清楚,图中所示,B树事实上是一种平衡的多叉查找树,也就是说最多可以开m个叉(m>=2),我们称之为m阶b树,为了体现本博客的良心之处,不同于其他地方都能看到2阶B树,这里特意画了一棵5阶B树 。

    img

    总的来说,m阶B树满足以下条件:

    • 每个节点至多可以拥有m棵子树。
    • 根节点,只有至少有2个节点(要么极端情况,就是一棵树就一个根节点,单细胞生物,即是根,也是叶,也是树)。
    • 非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整,图中5阶B树,每个节点至少有3个子树,也就是至少有3个叉)。
    • 非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An],,其中n表示该节点中保存的关键字个数,K为关键字且Ki<Ki+1,A为指向子树根节点的指针。
    • 从根到叶子的每一条路径都有相同的长度,也就是说,叶子节在相同的层,并且这些节点不带信息,实际上这些节点就表示找不到指定的值,也就是指向这些节点的指针为空。

    B树的查询过程和二叉排序树比较类似,从根节点依次比较每个结点,因为每个节点中的关键字和左右子树都是有序的,所以只要比较节点中的关键字,或者沿着指针就能很快地找到指定的关键字,如果查找失败,则会返回叶子节点,即空指针。

    例如查询图中字母表中的K:

    1. 从根节点P开始,K的位置在P之前,进入左侧指针。
    2. 左子树中,依次比较C、F、J、M,发现K在J和M之间。
    3. 沿着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树的特点可以总结为如下:

    1. 关键字集合分布在整颗树中。
    2. 任何一个关键字出现且只出现在一个节点中。
    3. 搜索有可能在非叶子节点结束。
    4. 其搜索性能等价于在关键字集合内做一次二分查找。
    5. B树在插入删除新的数据记录会破坏B-Tree的性质,因为在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。
    

    Plus版 — B+树

    作为B树的加强版,B+树与B树的差异在于

    • 有n棵子树的节点含有n个关键字(也有认为是n-1个关键字)。
    • 所有的关键字全部存储在叶子节点上,且叶子节点本身根据关键字自小而大顺序连接。
    • 非叶子节点可以看成索引部分,节点中仅含有其子树(根节点)中的最大(或最小)关键字。

    img

    B+树的查找过程,与B树类似,只不过查找时,如果在非叶子节点上的关键字等于给定值,并不终止,而是继续沿着指针直到叶子节点位置。因此在B+树,不管查找成功与否,每次查找都是走了一条从根到叶子节点的路径。

    B+树的特性如下:

    - 所有关键字都存储在叶子节上,且链表中的关键字恰好是有序的。
    - 不可能非叶子节点命中返回。
    - 非叶子节点相当于叶子节点的索引,叶子节点相当于是存储(关键字)数据的数据层。
    - 更适合文件索引系统。
    

    B*树

    B*树

       是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;
    

    B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2;

    B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

    B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了;如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

    所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

    带有顺序访问指针的B+Tree

    一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问指针。

    img

    如上图所示,在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的工作原理。

    img

    从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。上图展示了一个4 x 4的主存模型。

    主存的存取过程如下:

    当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

    写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

    这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

    磁盘存取原理

    上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

    下图是磁盘的整体结构示意图:

    img

    一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

    下图是磁盘结构的示意图:

    img

    盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

    当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

    img

    局部性原理与磁盘预读

    由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘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)。一般实际应用中,出度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))
    

    floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。

    MySQL索引实现

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

    MyISAM索引实现

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

    img

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

    img

    同样也是一棵B+树,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

    MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

    InnoDB索引实现

    虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

    第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

    img

    上图是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整型。

    第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,上图为定义在Col3上的一个辅助索引:

    img

    这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

    了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。再例如,用非单调的字段作为主键在InnoDB中不是个好主意,因为InnoDB数据文件本身是一棵B+Tree,非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

    加油

    B 树 / B+树区别

    B 树特性

    关键字集合分布在整颗树中;
    任何一个关键字出现且只出现在一个结点中;
    搜索有可能在非叶子结点结束;
    其搜索性能等价于在关键字全集内做一次二分查找;
    

    B+树

    有n棵子树的非叶子结点中含有n个关键字(b树是n-1个),这些关键字不保存数据,只用来索引,所有数据都保存在叶子节点(b树是每个关键字都保存数据)。
    所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
    所有的非叶子结点可以看成是索引部分,结点中仅含其子树中的最大(或最小)关键字。
    通常在b+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。
    同一个数字会在不同节点中重复出现,根节点的最大元素就是b+树的最大元素。
    

    b+树相比于b树的查询优势:

    ① B+树空间利用率更高, 可减少 I/O 次数
    
    ② 增删文件(节点)时, 效率更高
    
    ③B+树查询效率更加稳定
    

    小结

    ​ B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于

    走右结点;

    ​ B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键

    字范围的子结点;

    ​ 所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

    ​ B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点

    中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

    ​ B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率

    从1/2提高到2/3;

    参考资料

    [1] Baron Scbwartz等 著,王小东等 译;高性能MySQL(High Performance MySQL);电子工业出版社,2010

    [2] Michael Kofler 著,杨晓云等 译;MySQL5权威指南(The Definitive Guide to MySQL5);人民邮电出版社,2006

    [3] 姜承尧 著;MySQL技术内幕-InnoDB存储引擎;机械工业出版社,2011

    [4] D Comer, Ubiquitous B-tree; ACM Computing Surveys (CSUR), 1979

    [5] Codd, E. F. (1970). “A relational model of data for large shared data banks”. Communications of the ACM, , Vol. 13, No. 6, pp. 377-387

    [6] MySQL5.1参考手册 - http://dev.mysql.com/doc/refman/5.1/zh/index.html

    http://blog.codinglabs.org/articles/theory-of-mysql-index.html

    https://www.cnblogs.com/kxdblog/p/4893735.html

    https://www.cnblogs.com/boothsun/p/8970952.html#autoid-0-0-0

    https://www.cnblogs.com/xueqiuqiu/articles/8779029.html

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

    千次阅读 2019-05-21 00:17:36
    理解索引的特性 、索引的本质 、其他结构的问题 、B-Tree 和 B+Tree 、MySQL索引实现
  • MySQL索引底层数据结构索引到底是什么联合索引结构MyISAM索引文件和数据文件是分离的主键索引普通索引InnoDB索引实现主键索引普通索引 索引到底是什么 索引是帮助MySQL高效获取数据的 排好序 的 数据结构 索引存储...
  • Mysql索引底层原理分析, Mysql索引的本质 Mysql索引的底层原理 Mysql索引的实战经验 面试 问:数据库中最常见的慢查询优化方式是什么? 同学A:加索引。 问:为什么加索引能优化慢查询?同学A:…不知道同学B:因为...
  • Mysql索引底层及优化

    2021-04-14 15:07:18
    Mysql索引篇 最近在很多网站上看了索引的相关知识,各种说法的都有,但是又不是很全,有的概念很模糊,下面是由小编整理的Mysql索引知识点。 一.首先我们说下什么是索引,为什么要用索引 索引用于快速找出在某个列中...
  • mysql索引底层原理分析

    万次阅读 多人点赞 2018-09-23 00:01:40
    大家都知道索引的重要性,基本用法在上章《最全面的mysql索引知识大盘点》已分享过,本章主要是探索索引的底层实现原理。当然了,我们还是以mysql为基准进行探讨。 目录 前言:innodb和myisam的区别 1.物理磁盘...
  • MySql索引底层实现

    2017-09-17 20:58:25
    MySQL官方对于索引的定义为:索引是帮助MySQL高效获取数据的数据结构。即可以理解为:索引是数据结构。   我们知道,数据库查询是数据库最主要的功能之一,我们都希望查询数据的速度尽可能的快,因此数据库...
  • MySQL索引实现原理分析

    万次阅读 多人点赞 2018-10-10 17:59:07
    MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。MyISAM索引实现MyISAM引擎使用B+Tree作为索引结构,叶节点的data域存放的...
  • 索引(Index)是帮助MySQL高效获取数据的数据结构,为什么需要需要特定的数据结构呢?首先,顺序查找这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,更优秀的查找算法,比如二分查找(binary search)、二叉树...
  • MySQL - 剖析MySQL索引底层数据结构

    千次阅读 2020-07-18 16:51:14
    文章目录Pre Pre 什么是索引? 通俗的说就是为了提高效率专门设计的一种 排好序的数据结构。 怎么理解呢? 举个例子哈 如上数据 ,假设有个SQL select * from t where col2 = 22 ;
  • 深入理解 MySQL 索引底层原理 Mysql 作为互联网中非常热门的数据库,其底层的存储引擎和数据检索引擎的设计非常重要,尤其是 Mysql 数据的存储形式以及索引的设计,决定了 Mysql 整体的数据检索性能。 何为索引 ...
  • 1.应用场景 主要学习MySQL索引底层实现,数据结构与算法, 同时了解B+树/Hash索引的区别与优缺点,应用场景. 对于一般需求来说,B+树在数据库应用的场景更多,Hash适用一些特殊的需求,比如文件校验,密码学等 ...
  • 深入理解MySQL索引底层数据结构与算法

    万次阅读 多人点赞 2018-10-10 11:10:58
    (五) B+Tree(MySQL索引的真正存储结构) 三. 联合索引底层存储结构 一 理解索引的特性 索引是帮助MySQL高效获取数据的排好序的数据结构 索引存储在文件里 二 索引的各种存储结构及其优缺点 在开始讲这一小节...
  • 【2】索引底层原理实现以及主键索引、辅助索引、聚集索引、非聚集索引 MyISAM存储引擎 - 主键索引 MyISAM存储引擎 - 辅助索引 InnoDB存储引擎 - 主键索引 InnoDB存储引擎 - 辅助索引 【3】B+树和B-树的区别 【1...
  • 一步一步推导出 Mysql 索引底层数据结构。 Mysql 作为互联网中非常热门的数据库,其底层的存储引擎和数据检索引擎的设计非常重要,尤其是 Mysql 数据的存储形式以及索引的设计,决定了 Mysql 整体的数据检索性能...
  • Mysql索引底层原理与性能优化 在一般的开发中不会有碰到数据结构、算法的一些底层东西。但是了解了之后会对你的开发有很大的帮助。最近学习了一下。做一个笔记。更深的学习,请看相关书籍或视频。 一、索引是帮助...
  • Mysql索引底层数据结构(B树) 一.什么是B树 B - Trees是一种平衡的多叉树,称为B树(或B-树、B_树),也是数据结构中树形结构的一种。 二.什么是索引,为什么要用要索引 索引是帮助Mysql高效获取数据的排好序的数据...
  • Mysql索引底层数据结构与算法

    千次阅读 2020-01-31 18:33:58
    3. MyISAM和InnoDB的索引实现 4. 联合索引 5. 什么情况下应不建或少建索引 6. MySql在建立索引优化时需要注意的问题 1. 索引概念 索引概念:索引是帮助MySQL高效获取数据的排好序的数据结构,更通俗的说数据库...
  • 1.首先简单说下mysql的两大...你去你的mysql安装目录下看两个数据库的文件就会发现,MyiSam的文件比InnoDB的多出了一个文件:MYI (存索引的文件) 为什么这样做呢 ?当然是适应不同业务场景,通常InnoDB适用于大多
  • 深入理解 MySQL 索引底层的数据结构

    千次阅读 热门讨论 2021-02-27 23:04:08
    ### MySQL索引 #### 索引基础 #### 索引类型 ##### B-Tree索引 ##### 哈希索引 ##### 全文索引 #### 索引的优点 #### 高性能的索引 ##### 独立索引 ##### 多列索引 ##### 聚簇索引 ##### 覆盖索引
  • 【mysql知识点整理】 --- mysql索引底层数据结构

    千次阅读 多人点赞 2020-02-28 12:34:47
    文章目录1 什么是索引 1 什么是索引 索引是帮助MySQL高效的获取数据的数据结构。
  • 一文读懂mysql索引底层原理

    千次阅读 2019-03-19 10:59:00
    数据库的底层索引是用B树和B+树实现的,但是为什么使用的是它们,为什么不用红黑树? 红黑树等数据结构也可以用来实现索引,但是文件系统以及数据库系统普遍采用B-Tree/B+Tree作为索引结构.这是因为:索引本身也很大,...
  • MYSQL索引底层的数据结构

    千次阅读 2018-07-07 16:34:24
    特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTre...
  • 首先,大家要清楚mysql索引底层使用的树形数据结构是B+Tree,并不是B-Tree;为什么不是二叉树,红黑树,B-Tree呢,大家可以自行百度,这儿就不一一说明了。 先放一张B+Tree的图: 这是单值索引时底层的样子。用单值...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 67,608
精华内容 27,043
关键字:

mysql索引底层实现

mysql 订阅