精华内容
下载资源
问答
  • mysql索引数据结构
    万次阅读 多人点赞
    2018-08-26 11:55:58

    首先,数据库索引使用树来存储,因为树的查询效率高,而且二叉查找树还可以保持数据的有序。

    那么索引为什么没有使用二叉树来实现呢?

    其实从算法逻辑上讲,二叉查找树的查找速度和比较次数都是最小的,但是从Mysql的角度讲,我们不得不考虑一个现实问题:磁盘IO。

    查找都是索引操作,一般来说索引非常大,尤其是关系型数据库这种,当数据量比较大的时候,索引的大小有可能几个G甚至更多,数据量大的索引能达到亿级别,所以为了减少内存的占用,数据库索引是存储在外部磁盘上的

    当我们利用索引查询的时候,不可能把整个索引全部加载到内存,只能逐一加载每个磁盘页,磁盘页对应索引树的节点。

    那么Mysql衡量查询效率的标准就是磁盘IO次数。

    如果我们利用二叉树作为索引结构,那么磁盘的IO次数和索引树的高度是相关的。

    那么为了提高查询效率,就需要减少磁盘IO数。为了减少磁盘IO的次数,就需要尽量降低树的高度,需要把原来“瘦高”的树结构变的“矮胖”,树的每层的分叉越多越好,因此B树正好符合我们的要求,这也是B-树的特征之一。

    原来的二叉树一个节点只存储一个数据,要想把它变“矮胖”,就需要在一个节点存储多个数据,同时为了查找必须保持节点结构的有序,这样B树就应运而生了。

    B-树(B类树)的特点就是每层节点数目非常多,层数很少,目的就是为了就少磁盘IO次数。

    B-树是一种多路平衡查找树,它的每一个节点最多包含K个孩子,k称为B树的阶。k的大小取决于磁盘页的大小。

    一个m阶的B树具有如下几个特征:

    1.根结点至少有两个子女。

    2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m。

    3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m。

    4.所有的叶子结点都位于同一层。

    5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

    一个B树结构的具体例子。

    在B-树中进行查询时,在查询的中的比较次数其实不比二叉查找树少,尤其当单一节点中的元素数量很多时。

    可是相比磁盘IO的速度,内存中的耗时几乎可以忽略,所以只要树的高度足够低,IO次数足够少,就可以提高查询性能。

    相比之下节点内部元素多一点也没有关系,仅仅是多了几次内存交互,只要不超过磁盘页的大小即可。这就是B-树的优势之一。

    B树在插入和删除节点的时候如果导致树不平衡,就通过自动调整节点的位置来保持树的自平衡。

    非关系型数据库MongoDB使用B树作为数据库索引。

    大部分关系型数据库,比如Mysql,则使用B+树作为索引。

    B+树是基于B-树的一种变体,有着比B-树更高的查询性能。

    B+树和B-树有一些共同点,但是B+树也具备一些新的特征。

    一个m阶的B+树具有如下几个特征:

    1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。

    2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

    3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

    一个B+树结构的具体例子。

    从B+树的结构可以看出,B+树中的节点之间不但含有重复元素,而且叶子节点还用指针连在一起。

    在B+树中,每一个父节点的中的元素都出现在子节点中,是子节点的最大(或最小元素)。

    由于父节点的所有元素都出现在子节点,因此所有叶子节点包含了全量元素信息。

    并且每个叶子节点都有指向下一个叶子节点的指针,形成了有序链表。

    在B+树中,只有叶子节点才真正存储数据,非叶子节点不存储数据。

    使用B+树做索引的好处主要体现在查询性能上。

    在单元素查询的时候,B+树会自顶向下逐层查找节点,最终找到匹配的叶子节点。

    对于范围查询,比如查询范围为3~11的元素,B-树只能依靠繁琐的中序遍历,首先自顶向下查找范围的下限,然后中序遍历找到上限。

    B+树的范围查询则要简单的多,首先自顶向下查找范围的下限,然后只需要在叶子节点所在的链表上做遍历即可。

    B+树和B-树的区别: 

    B+树中间节点没有存储数据,只有叶节点存放数据,其余节点用来索引,所以同样大小的磁盘页可以容纳更多的节点元素,而B-树是每个索引节点都会有Data域。这就意味着,数据量相同的情况下,B+树的结构比B-树更加“矮胖”,因此查询是IO次数也更少。这就决定了B+树更适合用来存储外部数据,也就是所谓的磁盘数据。

    其次,B+树的查询必须最终查询到叶子节点,而B-树只要找到匹配元素即可,无论匹配元素处于中间节点还是叶子节点。

    因此,B-树的查询性能并不稳定(最好情况是只查根节点,最坏情况是查到叶子节点)。而B+树每一次查找都是稳定的。

    综合起来,B+树相比B-树的优势有三个:

    1.单一节点存储更多的元素,使得查询的IO次数更少。

    2.所有查询都要查找到叶子节点,查询性能稳定。

    3.所有叶子节点形成有序链表,便于范围查询。

    最后总结一下:

    数据库索引为什么不用AVL(平衡二叉树)?

    数据库索引是存储在磁盘上,磁盘IO操作比较耗时,为了提高查询效率就需要减少磁盘IO的次数。而磁盘IO次数和树的高度有关,所以为了减少磁盘IO就需要降低树的高度,这是查找的结构就可以把二叉树变成B类的树。

    数据库索引为什么用B+树而不用B-树?

    数据库索引采用B+树的主要原因是B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。

    那么MongoDB为什么使用B-树而不是B+树?

    至于MongoDB为什么使用B-树而不是B+树,可以从它的设计角度来考虑,它并不是传统的关系性数据库,而是以Json格式作为存储的nosql,目的就是高性能,高可用,易扩展。首先它摆脱了关系模型,上面所述的范围查询的优点就没那么强烈了,其次Mysql由于使用B+树,数据都在叶节点上,每次查询都需要访问到叶节点,而MongoDB使用B-树,所有节点都有Data域,只要找到指定索引就可以进行访问,无疑单次查询平均快于Mysql(但侧面来看Mysql至少平均查询耗时差不多)。

    总体来说,Mysql选用B+树和MongoDB选用B-树还是以自己的需求来选择的。

    数据库索引为什么不用红黑树?

    首先看一下红黑树的特点:

    红黑树是一种自平衡的二叉查找树,除了符合二叉查找树的基本特征外,它还具有下列的附加特征。

    1.节点是红色或黑色。

    2.根节点是黑色。

    3.每个叶子节点都是黑色的空节点(NIL节点)。

    4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

    5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

    下图中这棵树,就是一颗典型的红黑树:

    这是因为这些规则限制,才保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍。

    当插入或删除节点的时候,红黑树的规则可能被打破。这时候就需要做出一些调整, 来继续维持我们的规则。

    那么在大规模数据存储的时候,红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低下的情况。磁盘查找存取的次数往往由树的高度所决定,所以,只要我们通过某种较好的树结构尽量减少树的高度,就可以提高查询性能。B树可以有多个子女,从几十到上千,可以降低树的高度。

    归结起来,使用B+树而不是用其他结构的原因就是为了减少磁盘IO的次数,减少数的高度,而B+树就很好的做到了这一点。

    那么什么情况下使用红黑树?红黑树和B树使用场合有什么不同?

    两者都是有序的数据结构,可用作数据容器。

    红黑树多用在内部排序,即全放在内存中的,微软STL的map和set的内部实现就是红黑树。
    B树多用在内存里放不下,大部分数据存储在外存上时。因为B树层数少,因此可以确保每次操作,读取磁盘的次数尽可能的少。

    在数据较小,可以完全放到内存中时,红黑树的时间复杂度比B树低。
    反之,数据量较大,外存中占主要部分时,B树因其读磁盘次数少,而具有更快的速度。

    参考:(1)程序员小灰--《什么是B-树?》

               (2)程序员小灰--《什么是B+树?》   

               (3)https://blog.csdn.net/ligupeng7929/article/details/79529072

               (4)https://bbs.csdn.net/wap/topics/250015323

    更多相关内容
  • MySQL索引数据结构

    千次阅读 2022-01-22 17:42:09
    索引及其优缺点2.1 索引概述2.2 优点2.3 缺点3. InnoDB中索引的推演3.1 索引之前的查找1. 在一个页中的查找2. 在很多页中查找3.2 设计索引1. 一个简单的索引设计方案2. InnoDB中的索引方案3.3 常见索引概念1. 聚簇...

    1.为什么使用索引

    索引是存储引擎用于快速找到数据记录的一种数据结构,就好比一本教课书的目录部分,通过目录中找到对应文章的页码,便可快速定位到需要的文章。MySQL中也是一样的道理,进行数据查找时,首先查看查询条件是否命中某条索引,符合则通过索引查找相关数据,如果不符合则需要全表扫描,即需要一条一条地查找记录,直到找到与条件符合的记录。
    image.png
    如上图所示,数据库没有索引的情况下,数据分布在硬盘不同的位置上面,读取数据时,摆臂需要前后摆动查找数据,这样操作非常消耗时间。如果数据顺序摆放,那么也需要从1到6行按顺序读取,这样就相当于进行了6次IO操作,依旧非常耗时。如果我们不借助任何索引结构帮助我们快速定位数据的话,我们查找Col2= 89这条记录,就要逐行去查找、去比较。从col2=34开始,进行比较,发现不是,继续下一行。我们当前的表只有不到10行数据,但如果表很大的话,有上千万条数据,就意味着要做很多很多次磁盘I/O才能找到。现在要查找Col2= 89这条记录。CPu必须先去磁盘查找这条记录,找到之后加载到内存,再对数据进行处理。这个过程最耗时间的就是磁盘I/O(涉及到磁盘的旋转时间(速度较快)、磁头的寻道时间(速度慢、费时))。

    假如给数据使用二叉树这样的数据结构进行存储,如下图所示:
    image.png
    对字段Col2添加了索引,就相当于在硬盘上为Col2维护了一个索引的数据结构,即这个二叉搜索树。二叉搜索树的每个结点存储的是(K,V) 结构,key是Col2,value是该key所在行的文件指针(地址)。比如:该二叉搜索树的根节点就是:(34 , 0x07)。现在对Col2添加了索引,这时再去查找Col2=89这条记录的时候会先去查找该二叉搜索树。读34到内存,89>34;继续右侧数据,读89到内存,89 ==89;找到数据返回。找到之后就根据当前结点的value快速定位到要查找的记录对应的地址。我们可以发现,只需要查找两次就可以定位到记录的地址,查询速度就提高了。
    这就是我们为什么要建索引,目的就是为了减少磁盘I/O的次数,加快查询速率。

    2. 索引及其优缺点

    2.1 索引概述

    MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构

    **索引的本质:**索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”,满足特定查找算法。这些数据结构以某种方式指向数据,这样就可以在这些数据结构的基础上实现高级查找算法。

    索引是在存储引擎中实现的,因此每种存储引擎的索引不一定完全相同,并且每种存储引擎不一定支持所有索引类型。同时,存储引擎可以定义每个表的最大索引数和最大索引长度。所有存储引擎支持每个表至多16个索引,总索引长度至多为256字节。有些存储引擎支持更多的索引数和更大的索引长度。

    2.2 优点

    (1)类似大学图书馆建书目索引,提高数据检索的效率,降低数据库的IO成本,这也是创建索引最主要的原因。
    (2)通过创建唯一索引,可以保证数据库表中每一行数据的唯一性。
    (3)在实现数据的参考完整性方面,可以加速表和表之间的连接。换句话说,对于有依赖关系的子表和父表联合查询时,可以提高查询速度。
    (4)在使用分组和排序子句进行数据查询时,可以显著减少查询中分组和排序的时间,降低了CPU的消耗。

    2.3 缺点

    增加索引也有许多不利的方面,主要表现在如下几个方面:
    (1)创建索引和维护索引要耗费时间,并且随着数据量的增加,所耗费的时间也会增加。
    (2)索引需要占磁盘空间,除了数据表占数据空间之外,每一个索引还要占一定的物理空间,存储在磁盘上,如果有大量的索引,索引文件就可能比数据文件更快达到最大文件尺寸。
    (3)虽然索引大大提高了查询速度,同时却会降低更新表的速度。当对表中的数据进行增加、删除和修改的时候,索引也要动态地维护,这样就降低了数据的维护速度。

    因此,选择使用索引时,需要综合考虑索引的优点和缺点。

    提示:
    索引可以提高查询的速度,但是会影响插入记录的速度。这种情况下,最好的办法是先删除表中的索引,然
    后插入数据,插入完成后再创建索引。

    3. InnoDB中索引的推演

    3.1 索引之前的查找

    先来看一个精确匹配的例子:

    SELECT [列名] FROM 表名WHERE 列名 = xxx;

    1. 在一个页中的查找

    假设目前表中的记录比较少,所有的记录都可以被存放到一个页中,在查找记录的时候可以根据搜索条件的不同分为两种情况 :

    • 以主键为搜索条件

    可以在页目录中使用二分法快速定位到对应的槽,然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

    • 以其他列作为搜索条件

    因为在数据页中并没有对非主键列建立所谓的页目录,所以我们无法通过二分法快速定位相应的槽。这种情
    况下只能从最小记录开始依次遍历单链表中的每条记录,然后对比每条记录是不是符合搜索条件。很显然,这种查找的效率是非常低的。

    2. 在很多页中查找

    在没有索引的情况下,不论是根据主键列或者其他列的值进行查找,由于我们并不能快速的定位到记录所在的页,所以只能从第一个页沿着双向链表一直往下找,在每一个页中根据我们上面的查找方式去查找指定的记录。因为要遍历所有的数据页,所以这种方式显然是超级耗时的。如果一个表有一亿条记录呢?此时索引应运而生。
    image.png

    3.2 设计索引

    建一个表:

    mysql> CREATE TABLE index_demo (
    -> c1 INT,
    -> c2 INT,
    -> c3 CHAR(1),
    -> PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact ;

    这个新建的 index_demo 表中有2个INT类型的列,1个CHAR(1)类型的列,而且我们规定了c1列为主键,
    这个表使用 Compact 行格式来实际存储记录的。这里我们简化了index_demo表的行格式示意图:
    image.png
    我们只在示意图里展示记录的这几个部分:

    • record_type:记录头信息的一项属性,表示记录的类型,0表示普通记录、2表示最小记录、3表示最大记录、1表示目录项的记录。
    • next_record:记录头信息的一项属性,表示下一条地址相对于本条记录的地址偏移量,我们用箭头来表明下一条记录是谁。​
    • 各个列的值:这里只记录在index_demo表中的三个列,分别是c1、c2和c3。
    • 其他信息:除了上述3种信息以外的所有信息,包括其他隐藏列的值以及记录的额外信息。

    将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样:
    image.png
    把一些记录放到页里的示意图就是:
    image.png

    1. 一个简单的索引设计方案

    我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢?因为各个页中的记录并没有规律,我们并不知道我们的搜索条件匹配哪些页中的记录,所以不得不依次遍历所有的数据页。所以如果我们想快速的定位到需要查找的记录在哪些数据页中该咋办?我们可以为快速定位记录所在的数据页而建立一个目录,建这个目录必须完成下边这些事:

    • 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

    假设:每个数据页最多能存放3条记录(实际上一个数据页非常大,可以存放下好多记录)。有了这个假设之
    后我们向index_demo表插入3条记录:

    mysql> INSERT INTO index_demo VALUES(1,4,‘u’),(3,9,‘d’),(5,3,‘y’);
    Query oK,3 rows affected (0.01 sec)
    Records: 3 Duplicates: 0 Warnings: 8

    那么这些记录已经按照主键值的大小串联成一个单向链表了,如图所示 :
    image.png
    从图中可以看出来,index_demo表中的3条记录都被插入到了编号为10的数据页中了。此时我们再来插入
    —条记录:

    mysql> INSERT INTO index_demo VALUES(4,4, ‘a’ );

    因为页10最多只能放3条记录,所以我们不得不再分配一个新页:
    image.png
    注意,新分配的数据页编号可能并不是连续的。它们只是通过维护着上一个页和下一个页的编号而建立了链表关系。另外,页10中用户记录最大的主键值是5,而页28中有一条记录的主键值是4,因为5>4,所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求,所以在插入主键值为4的记录的时候需要伴随着一次记录移动,也就是把主键值为5的记录移动到页28中,然后再把主键值为4的记录插入到页10中,这个过程的示意图如下:
    image.png
    这个过程表明了在对页中的记录进行增删改操作的过程中,我们必须通过一些诸如记录移动的 操作来始终保证这个状态一直成立:下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们称为页分裂。

    • 给所有的页建立一个目录项。

    由于数据页的编号可能是不连续的,所以在向index_demo表中插入许多条记录后,可能是这样的效果 :
    image.png
    因为这些16KB的页在物理存储上是不连续的,所以如果想从这么多页中根据主键值快速定位某些记录所在的页,我们需要给它们做个目录,每个页对应一个目录项,每个目录项包括下边两个部分:

    • 页的用户记录中最小的主键值,我们用key来表示。
    • 页号,我们用page_no表示。

    所以我们为上边几个页做好的目录就像这样 :
    image.png
    以 页28 为例,它对应 目录项2 ,这个目录项中包含着该页的页号 28 以及该页中用户记录的最小主
    键值 5 。我们只需要把几个目录项在物理存储器上连续存储(比如:数组),就可以实现根据主键
    值快速查找某条记录的功能了。比如:查找主键值为 20 的记录,具体查找过程分两步:

    1. 先从目录项中根据 二分法 快速确定出主键值为 20 的记录在 目录项3 中(因为 12 < 20 <
      209 ),它对应的页是 页9 。
    2. 再根据前边说的在页中查找记录的方式去 页9 中定位具体的记录。
      至此,针对数据页做的简易目录就搞定了。这个目录有一个别名,称为 索引 。

    2. InnoDB中的索引方案

    ① 迭代1次:目录项记录的页

    • 0:普通的用户记录
    • 1:目录项记录
    • 2:最小记录
    • 3:最大记录

    我们把前边使用到的目录项放到数据页中的样子就是这样:

    image.png
    从图中可以看出来,我们新分配了一个编号为30的页来专门存储目录项记录。这里再次强调 目录项记录和普通的 用户记录 的不同点

    • 目录项记录 的 record_type 值是1,而 普通用户记录 的 record_type 值是0。
    • 目录项记录只有 主键值和页的编号 两个列,而普通的用户记录的列是用户自己定义的,可能包含很多列,另外还有InnoDB自己添加的隐藏列。

    相同点:两者用的是一样的数据页,都会为主键值生成 Page Directory (页目录),从而在按照主键值进行查找时可以使用 二分法 来加快查询速度。

    现在以查找主键为 20 的记录为例,根据某个主键值去查找记录的步骤就可以大致拆分成下边两步:

    1. 先到存储 目录项记录 的页,也就是页30中通过页目录使用二分法 快速定位到对应目录项,因为 12 < 20 <209 ,所以定位到对应的记录所在的页就是页9。
    2. 再到存储用户记录的页9中根据 二分法 快速定位到主键值为 20 的用户记录。

    此时需要 2次 磁盘IO。

    ② 迭代2次:多个目录项纪录的页

    image.png
    从图中可以看出,我们插入了一条主键值为320的用户记录之后需要两个新的数据页:

    • 为存储该用户记录而新生成了页31。
    • 因为原先存储目录项记录的页30的容量已满(我们前边假设只能存储4条目录项记录),所以不得不需要一个新的页32来存放页31对应的目录项。

    现在因为存储目录项记录的页不止一个,所以如果我们想根据主键值查找一条用户记录大致需要3个步骤,以查找主键值为20的记录为例:

    1. 确定目录项记录页
      我们现在的存储目录项记录的页有两个,即页30和页32,又因为页30表示的目录项的主键值的范围是[1,
      320),页32表示的目录项的主键值不小于320,所以主键值为20的记录对应的目录项记录在页30中。
    2. 通过目录项记录页确定用户记录真实所在的页。
    3. 在真实存储用户记录的页中定位到具体的记录。

    假如没有找到,还需要到第二个目录页中寻找,则进行了3次 IO。
    ③ 迭代3次:目录项记录页的目录页

    image.png
    如图,我们生成了一个存储更高级目录项的 页33 ,这个页中的两条记录分别代表页30和页32,如果用
    户记录的主键值在 [1, 320) 之间,则到页30中查找更详细的目录项记录,如果主键值 不小于320 的话,就到页32中查找更详细的目录项记录。

    若查找C1=20这条记录,会进行三次IO

    我们可以用下边这个图来描述它:
    image.png
    这个数据结构,它的名称是 B+树 。
    ④ B+Tree
    树的层次越低,IO次数就越少。
    一个B+树的节点其实可以分成好多层,规定最下边的那层,也就是存放我们用户记录的那层为第 0 层,
    之后依次往上加。之前我们做了一个非常极端的假设:存放用户记录的页 最多存放3条记录 ,存放目录项
    记录的页 最多存放4条记录 。其实真实环境中一个页存放的记录数量是非常大的,假设所有存放用户记录
    的叶子节点代表的数据页可以存放 100条用户记录 ,所有存放目录项记录的内节点代表的数据页可以存
    放 1000条目录项记录 ,那么:

    • 如果B+树只有1层,也就是只有1个用于存放用户记录的节点,最多能存放 100 条记录。
    • 如果B+树有2层,最多能存放 1000×100=10,0000 条记录。
    • 如果B+树有3层,最多能存放 1000×1000×100=1,0000,0000 条记录。
    • 如果B+树有4层,最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。相当多的记
      录!!!

      你的表里能存放 100000000000 条记录吗?所以一般情况下,我们 用到的B+树都不会超过4层 ,那我们
      通过主键值去查找某条记录最多只需要做4个页面内的查找(查找3个目录项页和一个用户记录页),又
      因为在每个页面内有所谓的 Page Directory (页目录),所以在页面内也可以通过 二分法 实现快速
      定位记录。

    3.3 常见索引概念

    索引按照物理实现方式,索引可以分为 2 种:聚簇(聚集)和非聚簇(非聚集)索引。我们也把非聚集索引称为二级索引或者辅助索引

    1. 聚簇索引

    聚簇索引并不是一种单独的索引类型,而是一种数据存储方式(所有的用户记录都存储在了叶子节点),也就是
    所谓的索引即数据,数据即索引。

    术语"聚簇""表示数据行和相邻的键值聚簇的存储在一起。

    特点:

    1. 使用记录主键值的大小进行记录和页的排序,这包括三个方面 的含义:
    • 页内的记录是按照主键的大小顺序排成一个单向链表。
    • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
    • 存放目录项记录的页分为不同的层次,在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
    1. B+树的叶子节点存储的是完整的用户记录。
      所谓完整的用户记录,就是指这个记录中存储了所有列的值(包括隐藏列)。

    我们把具有这两种特性的B+树称为聚簇索引,所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MysQL语句中显式的使用INDEX语句去创建,InnoDB存储引擎会自动的为我们创建聚簇索引。

    优点:

    • 数据访问更快,因为聚簇索引将索引和数据保存在同一个B+树中,因此从聚簇索引中获取数据比非聚簇索引更快
    • 聚簇索引对于主键的排序查找和范围查找速度非常快
    • 按照聚簇索引排列顺序,查询显示一定范围数据的时候,由于数据都是紧密相连,数据库不用从多个数据块中提取数据,所以节省了大量的io操作。

    缺点:

    • 插入速度严重依赖于插入顺序,按照主键的顺序插入是最快的方式,否则将会出现页分裂,严重影响性能。因此,对于InnoDB表,我们一般都会定义一个自增的ID列为主键
    • 更新主键的代价很高,因为将会导致被更新的行移动。因此,对于InnoDB表,我们一般定义主键为不可更新
    • 二级索引访问需要两次索引查找,第一次找到主键值,第二次根据主键值找到行数据

    限制 :

    • 对于MySQL数据库目前只有InnoDB数据引擎支持聚簇索引,而MylSAM并不支持聚簇索引。
    • 由于数据物理存储排序方式只能有一种,所以每个MySQL的表只能有一个聚簇索引。一般情况下就是该表的主键。
    • 如果没有定义主键,Innodb会选择非空的唯一索引代替。如果没有这样的索引,Innodb会隐式的定义一个主键来作为聚簇索引。
    • 为了充分利用聚簇索引的聚簇的特性,所以innodb表的主键列尽量选用有序的顺序id,而不建议用无序的id,比如UUID、MD5、HASH、字符串列作为主键无法保证数据的顺序增长。

    2. 二级索引(辅助索引、非聚簇索引)

    如果我们想以别的列作为搜索条件该怎么办呢?肯定不能是从头到尾沿着链表依次遍历记录一遍。

    答案 : 我们可以多建几棵B+树,不同的B+树中的数据采用不同的排序规则。比方说我们用c2列的大小作为数据页、页中记录的排序规则,再建一棵B+树,效果如下图所示 :

    image.png
    假如现在找C2=4的记录,select * form C2=4 ; 但是在这个B+树中没有C3,因此需要回表。
    概念回表 我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值,所以如果我们想根
    据c2列的值查找到完整的用户记录的话,仍然需要到 聚簇索引 中再查一遍,这个过程称为 回表 。也就
    是根据c2列的值查询一条完整的用户记录需要使用到 2 棵B+树!
    问题:为什么我们还需要一次 回表 操作呢?直接把完整的用户记录放到叶子节点不OK吗?
    回答:
    如果把完整的用户记录放到叶子节点是可以不用回表。但是太占地方了,相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍,这就有点太浪费存储空间了。

    因为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录,所以这种B+树也被称为二级索引(英文名secondary index),或者辅助索引。由于我们使用的是c2列的大小作为B+树的排序规则,所以我们也称这个B+树是为c2列建立的索引。

    非聚簇索引的存在不影响数据在聚簇索引中的组织,所以一张表可以有多个非聚簇索引。
    image.png
    小结 : 聚簇索引与非聚簇索引的原理不同,在使用上也有一些区别:

    1. 聚簇索引的叶子节点存储的就是我们的数据记录,非聚簇索引的叶子节点存储的是数据位置。非聚簇索引不会影响数据表的物理存储顺序。

    2. 一个表只能有一个聚簇索引,因为只能有一种排序存储的方式,但可以有多个非聚簇索引,也就是多个索引目录提供数据检索。

    3. 使用聚簇索引的时候,数据的查询效率高,但如果对数据进行插入,删除,更新等操作,效率会比非聚簇索引低。

    3. 联合索引

    我们也可以同时以多个列的大小作为排序规则,也就是同时为多个列建立索引,比方说我们想让B+树按照c2和c3列的大小进行排序,这个包含两层含义:

    • 先把各个记录和页按照c2列进行排序。

    • 在记录的c2列相同的情况下,采用c3列进行排序
      image.png
      如图所示,我们需要注意以下几点:

    • 每条目录项记录都由c2、c3、页号这三个部分组成,各条记录先按照c2列的值进行排序,如果记录的c2列相同,则按照c3列的值进行排序。

    • B+树叶子节点处的用户记录由c2、c3和主键c1列组成。

    注意一点,以c2和c3列的大小为排序规则建立的B+树称为联合索引,本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的,不同点如下:

    • 建立联合索引只会建立如上图一样的1棵B+树。
    • 为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。

    查找 C2=4,C3=u 的记录,找到页35。

    3.4 InnoDB的B+树索引的注意事项

    1. 根页面位置万年不动
    相反顺序创建。(自上而下)
    2. 内节点中目录项记录的唯一性
    我们知道B+树索引的内节点中目录项记录的内容是索引列 +页号的搭配,但是这个搭配对于二级索引来说有点
    儿不严谨。还拿index_demo表为例,假设这个表中的数据是这样的 :
    image.png
    如果二级索引中目录项记录的内容只是索引列+页号的搭配的话,那么为c2列建立索引后的B+树应该长这样:
    image.png
    如果我们想新插入一行记录,其中c1、c2、c3的值分别是:(9、1、‘c’),那么在修改这个为c2列建立的二
    级索引对应的B+树时便碰到了个大问题:由于页3中存储的目录项记录是由c2列+页号的值构成的,页3中的
    两条目录项记录对应的c2列的值都是1,而我们新插入的这条记录的c2列的值也是1,那我们这条新插入的记录
    到底应该放到页4中,还是应该放到页5中啊? 答案是:对不起,懵了。

    为了让新插入记录能找到自己在那个页里,我们**需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。**所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的 :

    • 索引列的值
    • 主键值
    • 页号

    也就是我们把主键值也添加到二级索引内节点中的目录项记录了,这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的,所以我们为c2列建立二级索引后的示意图实际上应该是这样子的 :
    image.png
    3. 一个页面最少存储2条记录

    4. MyISAM中的索引方案

    B树索引适用存储引擎如表所示:

    索引 / 存储引擎MyISAMInnoDBMemory
    B-Tree索引支持支持支持

    即使多个存储引擎支持同一种类型的索引,但是他们的实现原理也是不同的。Innodb和MyISAM默认的索引是Btree索引;而Memory默认的索引是Hash索引。

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

    4.2 MyISAM索引的原理

    下图是MyISAM索引的原理图。

    image.png
    如果我们在Col2上建立一个二级索引,则此索引的结构如下图所示:
    image.png

    4.3 MyISAM 与 InnoDB对比

    MyISAM的索引方式都是“非聚簇”的,与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别:

    1. 在InnoDB存储引擎中,我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录,而在MyISAM中却需要进行一次回表操作,意味着MyISAM中建立的索引相当于全部都是二级索引。

    2. InnoDB的数据文件本身就是索引文件,而MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。

    3. InnoDB的非聚簇索引data域存储相应记录主键的值,而MyISAM索引记录的是地址。换句话说,InnoDB的所有非聚簇索引都引用主键作为data域。

    4. MyISAM的回表操作是十分快速的,因为是拿着地址偏移量直接到文件中取数据的,反观InnoDB是通过获取主键之后再去聚簇索引里找记录,虽然说也不慢,但还是比不上直接用地址去访问。

    5. InnoDB要求表必须有主键(MyISAM可以没有)。如果没有显式指定,则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整型。

    image.png

    5. 索引的代价

    索引是个好东西,可不能乱建,它在空间和时间上都会有消耗:

    • 空间上的代价

    每建立一个索引都要为它建立一棵B+树,每一棵B+树的每一个节点都是一个数据页,一个页默认会占用16KB的存储空间,一棵很大的B+树由许多数据页组成,那就是很大的一片存储空间。

    • 时间上的代价

    每次对表中的数据进行增、删、改操作时,都需要去修改各个B+树索引。而且我们讲过,B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录,还是内节点中的记录(也就是不论是用户记录还是目录项记录)都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏,所以存储引擎需要额外的时间进行一些记录移位,页面分裂、页面回收等操作来维护好节点和记录的排序。如果我们建了许多索引,每个索引对应的B+树都要进行相关的维护操作,会给性能拖后腿。

    6. MySQL数据结构选择的合理性

    6.1 全表遍历

    6.2 Hash结构

    image.png
    image.png

    上图中哈希函数h有可能将两个不同的关键字映射到相同的位置,这叫做 碰撞 ,在数据库中一般采用 链
    接法 来解决。在链接法中,将散列到同一槽位的元素放在一个链表中,如下图所示:
    image.png
    实验:体会数组和hash表的查找方面的效率区别

    // 算法复杂度为 O(n)
    @Test
    public void test1(){
        int[] arr = new int[100000];
        for(int i = 0;i < arr.length;i++){
        	arr[i] = i + 1;
    	}
        long start = System.currentTimeMillis();
        for(int j = 1; j<=100000;j++){
        	int temp = j;
            for(int i = 0;i < arr.length;i++){
                if(temp == arr[i]){
                    break;
                }
            }
        }
        long end = System.currentTimeMillis();
        System.out.println("time: " + (end - start));   // time: 823
    }
    // 算法复杂度为 O(1)
    @Test
    public void test2(){
        HashSet<Integer> set = new HashSet<>(100000);
        for(int i = 0;i < 100000;i++){
        	set.add(i + 1);
        }
        long start = System.currentTimeMillis();
        for(int j = 1; j<=100000;j++) {
        	int temp = j;
        	boolean contains = set.contains(temp);
        }
        long end = System.currentTimeMillis();
        System.out.println("time: " + (end - start));   // time: 5
    }
    

    Hash结构效率高,那为什么索引结构要设计成树型呢?
    Hash索引适用存储引擎如表所示:

    索引 / 存储引擎MyISAMInnoDBMemory
    HASH索引不支持不支持支持

    Hash索引的适用性:

    image.png

    采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点,特别是当 B+
    树比较深的时候,通过自适应 Hash 索引可以明显提高数据的检索效率。

    我们可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash,比如:

    mysql> show variables like ‘%adaptive_hash_index’;

    image.png

    6.3 二叉搜索树

    如果我们利用二叉树作为索引结构,那么磁盘的IO次数和索引树的高度是相关的。

    1. ** 二叉搜索树的特点 **
    2. ** 查找规则**
      image.png

    创造出来的二分搜索树如下图所示:
    image.png
    为了提高查询效率,就需要减少磁盘IO数。为了减少磁盘IO的次数,就需要尽量降低树的高度,需要把原来“瘦高”的树结构变的“矮胖”,树的每层的分叉越多越好。

    6.4 AVL树

    image.png
    针对同样的数据,如果我们把二叉树改成 M 叉树 (M>2)呢?当 M=3 时,同样的 31 个节点可以由下面
    的三叉树来进行存储:
    image.png

    6.5 B-Tree

    B 树的结构如下图所示:

    image.png
    一个 M 阶的 B 树(M>2)有以下的特性:

    1. 根节点的儿子数的范围是 [2,M]。
    2. 每个中间节点包含 k-1 个关键字和 k 个孩子,孩子的数量 = 关键字的数量 +1,k的取值范围为[ceil(M/2), M]。
    3. 叶子节点包括 k-1 个关键字(叶子节点没有孩子),k 的取值范围为 [ceil(M/2),M]。
    4. 假设中间节点节点的关键字为:Key[1], Key[2], …,Key[k-1],且关键字按照升序排序,即 Key[i] <Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围,也就是对应着 k个指针,即为:P[1], P[2], …, P[k],其中 P[1] 指向关键字小于 Key[1] 的子树,P[i]指向关键字属于 (Key[i-1], Key[i]) 的子树,P[k] 指向关键字大于 Key[k-1] 的子树。
    5. 所有叶子节点位于同一层。

    上面那张图所表示的 B 树就是一棵 3 阶的 B 树。我们可以看下磁盘块2,里面的关键字为(8,12),它有 3 个孩子 (3,5),(9,10) 和 (13,15),你能看到(3,5) 小于 8,(9,10) 在 8 和 12 之间,而 (13,15) 大于12,刚好符合刚才我们给出的特征。

    然后我们来看下如何用 B 树进行查找。假设我们想要查找的关键字是9,那么步骤可以分为以下几步:

    1. 我们与根节点的关键字 (17,35)进行比较,9 小于 17 那么得到指针 P1;
    2. 按照指针 P1 找到磁盘块 2,关键字为(8,12),因为 9 在 8 和 12之间,所以我们得到指针 P2;
    3. 按照指针 P2 找到磁盘块 6,关键字为(9,10),然后我们找到了关键字 9。

    你能看出来在 B树的搜索过程中,我们比较的次数并不少,但如果把数据读取出来然后在内存中进行比较,这个时间就是可以忽略不计的。而读取磁盘块本身需要进行I/O操作,消耗的时间比在内存中进行比较所需要的时间要多,是数据查找用时的重要因素。B树相比于平衡二叉树来说磁盘 I/O操作要少,在数据查询中比平衡二叉树效率要高。所以只要树的高度足够低,IO次数足够少,就可以提高查询性能。

    再举例1:

    image.png

    6.6 B+Tree

    • MySQL官网说明
      image.png
      B+ 树和 B 树的差异:
    1. 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数,而 B树中,孩子数量 = 关键字数+1。
    2. 非叶子节点的关键字也会同时存在在子节点中,并且是在子节点中所有关键字的最大(或最小)。
    3. 非叶子节点仅用于索引,不保存数据记录,跟记录有关的信息都放在叶子节点中。而 B树中,非叶子节点既保存索引,也保存数据记录。
    4. 所有关键字都在叶子节点出现,叶子节点构成一个有序链表,而且叶子节点本身按照关键字的大小从小到大顺序链接。

    B 树和 B+ 树都可以作为索引的数据结构,在 MySQL 中采用的是 B+ 树。
    但B树和B+树各有自己的应用场景,不能说B+树完全比B树好,反之亦然。

    思考题:为了减少IO,索引树会一次性加载吗?

    思考题:B+树的存储能力如何?为何说一般查找行记录,最多只需1~3次磁盘IO

    思考题:为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引?

    思考题:Hash 索引与 B+ 树索引的区别

    思考题:Hash 索引与 B+ 树索引是在建索引的时候手动指定的吗?

    6.7 R树

    R-Tree在MySQL很少使用,仅支持 geometry数据类型 ,支持该类型的存储引擎只有myisam、bdb、
    innodb、ndb、archive几种。举个R树在现实领域中能够解决的例子:查找20英里以内所有的餐厅。如果
    没有R树你会怎么解决?一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中,一个字段记
    录经度,另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息,然后计算是否满
    足要求。如果一个地区有100家餐厅的话,我们就要进行100次位置计算操作了,如果应用到谷歌、百度
    地图这种超大数据库中,这种方法便必定不可行了。R树就很好的 解决了这种高维空间搜索问题 。它把B
    树的思想很好的扩展到了多维空间,采用了B树分割空间的思想,并在添加、删除操作时采用合并、分解
    结点的方法,保证树的平衡性。因此,R树就是一棵用来 存储高维数据的平衡树 。相对于B-Tree,R-Tree
    的优势在于范围查找。

    索引 / 存储引擎MyISAMInnoDBMemory
    R-Tree索引支持支持不支持

    附录:算法的时间复杂度

    同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
    image.png

    展开全文
  • mysql索引数据结构

    千次阅读 2022-03-27 14:43:57
    对字段Col2添加了索引,就相当于在硬盘上为col 2维护了一个索引数据结构,即这个二叉搜索树。二叉搜索树的每个结点存储的是(K,V)结构,key是Col 2,value是该key所在行的文件指针(地址)。比如:该二

    为什么使用索引

    在这里插入图片描述

    我们假如不使用索引的话,就像我们左边的这样,造成全文索引
    加入索引的话,像我们右边的这样,那么它的速度就会快上很多。

    打个比方,假如我们需要查字典的话,索引就像我们的目录一样,没有索引,我们就只能一页一页去找。而加上索引之后,我们可以根据目录来快速查找我们所需要的东西

    在这里插入图片描述

    对字段Col2添加了索引,就相当于在硬盘上为col 2维护了一个索引的数据结构,即这个二叉搜索树。二叉搜索树的每个结点存储的是(K,V)结构,key是Col 2,value是该key所在行的文件指针(地址)。比如:该二叉搜索树的根节点就是:(34,0x07)。现在对Ccol2添加了索引,这时再去查找Col 2=89这条记录的时候会先去查找该二叉搜索树(二叉树的遍历查找)。读34到内存,89>34;继续右侧数据,读s9到内存,89 ==- 89;找到数据返回。找到之后就根据当前结点的value快速定位到要查找的记录对应的地址。我们可以发现,只需要查找两次就可以定位到记录的地址,查询速度就提高了。

    这就是我们为什么要建索引,目的就是为了减少磁盘 I/O 的次数,加快查询速率。

    索引及其优缺点

    索引概述

    MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构
    索引的本质:索引是数据结构。你可以简单理解为“排好序的快速查找数据结构”,满足特定查找算法。这些数据结构以某种方式指向数据, 这样就可以在这些数据结构的基础上实现 高级查找算法

    优点:

    (1)类似大学图书馆建书目索引,提高数据检索的效率,降低 数据库的IO成本 ,这也是创建索引最主要的原因。
    (2)通过创建唯一索引,可以保证数据库表中每一行 数据的唯一性
    (3)在实现数据的参考完整性方面,可以 加速表和表之间的连接。换句话说,对于有依赖关系的子表和父表联合查询时,可以提高查询速度
    (4)在使用分组和排序子句进行数据查询时,可以显著 减少查询中分组和排序的时间 ,降低了CPU的消耗

    缺点:

    (1)创建索引和维护索引要 耗费时间 ,并且随着数据量的增加,所耗费的时间也会增加。
    (2)索引需要占 磁盘空间 ,除了数据表占数据空间之外,每一个索引还要占一定的物理空间, 存储在磁盘上 ,如果有大量的索引,索引文件就可能比数据文件更快达到最大文件尺寸。
    (3)虽然索引大大提高了查询速度,同时却会 降低更新表的速度 。当对表中的数据进行增加、删除和修改的时候,索引也要动态地维护,这样就降低了数据的维护速度。

    提示:
    索引可以提高查询的速度,但是会影响插入记录的速度。这种情况下,最好的办法是先删除表中的索引,然后插入数据,插入完成后再创建索引。

    需要注意的是:索引是在具体的存储引擎中实现的,不同的存储引擎,索引的数据结构就有可能不一样。

    InnoDB中的索引

    在这里插入图片描述

    这个数据结构,就是我们的B+树

    B+Tree

    不论是存放用户记录的数据页,还是存放目录项记录的数据页,我们都把它们存放到B+树这个数据结构中了,所以我们也称这些数据页为节点。从图中可以看出,我们的实际用户记录其实都存放在B+树的最底层的节点上,这些节点也被称为叶子节点,其余用来存放目录项的节点称为非叶子节点或者内节点,其中B+树最上边的那个节点也称为根节点。

    为什么说我们用到的B+树都不会超过四层呢???

    在 MySQL 中我们的 InnoDB 页的大小默认是 16kb。
    假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录,相当于一条数据占160字节,所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录(因为目录页的字段没有叶子结点的字段多,所以一般可以多存储一点) ,那么:

    • 如果B+树只有1层,也就是只有1个用于存放用户记录的节点,最多能存放 100 条记录
    • 如果B+树有2层,最多能存放 1000×100=10,0000 条记录。
    • 如果B+树有3层,最多能存放 1000×1000×100=1,0000,0000 条记录。
    • 如果B+树有4层,最多能存放 1000×1000×1000×100=1000,0000,0000 条记录。相当多的记录!!!

    你的表里能存放一千万条记录吗??所以一般情况下,我们 用到的B+树都不会超过4层 ,那我们通过主键值去查找某条记录最多只需要做4个页面内的查找(查找3个目录项页和一个用户记录页),又因为在每个页面内有所谓的 Page Directory(页目录),所以在页面内也可以通过 二分法 实现快速定位记录。

    常见索引概念

    索引按照物理实现方式,索引可以分为 2 种:聚簇(聚集)和非聚簇(非聚集)索引。我们也把非聚集索引称为二级索引或者辅助索引。

    聚簇索引

    在这里插入图片描述

    聚簇索引并不是一种单独的索引类型,而是一种数据存储方式(所有的用户记录都存储在了叶子节点),也就是所谓的索引即数据,数据即索引

    术语"聚簇"表示数据行和相邻的键值聚簇的存储在一起。

    特点:

    • 使用记录主键值的大小进行记录和页的排序,这包括三个方面的含义:
      页内 的记录是按照主键的大小顺序排成一个 单向链表。
      各个存放 用户记录的页 也是根据页中用户记录的主键大小顺序排成一个 双向链表 。
      存放目录项记录的页 分为不同的层次,在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个 双向链表。
    • B+树的 叶子节点 存储的是完整的用户记录。
      所谓完整的用户记录,就是指这个记录中存储了所有列的值(包括隐藏列)。

    我们把具有这两种特性的B+树称为聚簇索引,所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MysQL语句中显式的使用INDEX语句去创建,InnoDB存储引擎会自动的为我们创建聚簇索引。

    优点:

    • 数据访问更快 ,因为聚簇索引将索引和数据保存在同一个B+树中,因此从聚簇索引中获取数据比非聚簇索引更快
    • 聚簇索引对于主键的 排序查找 和 范围查找 速度非常快
    • 按照聚簇索引排列顺序,查询显示一定范围数据的时候,由于数据都是紧密相连,数据库不用从多个数据块中提取数据,所以 节省了大量的io操作

    缺点:

    • 插入速度严重依赖于插入顺序 ,按照主键的顺序插入是最快的方式,否则将会出现页分裂,严重影响性能。因此,对于InnoDB表,我们一般都会定义一个自增的ID列为主键
    • 更新主键的代价很高 ,因为将会导致被更新的行移动。因此,对于InnoDB表,我们一般定义主键为不可更新
    • 二级索引访问需要两次索引查找 ,第一次找到主键值,第二次根据主键值找到行数据

    限制:

    • 对于MySQL数据库目前只有InnoDB数据引擎支持聚簇索引,而MylSAM并不支持聚簇索引。
    • 由于数据物理存储排序方式只能有一种,所以每个MySQL的表只能有一个聚簇索引。一般情况下就是该表的主键。
    • 如果没有定义主键,Innodb会选择非空的唯一索引代替。如果没有这样的索引,Innodb会隐式的定义一个主键来作为聚簇索引。
    • 为了充分利用聚簇索引的聚簇的特性,所以innodb表的主键列尽量选用有序的顺序id,而不建议用无序的id,比如UUID、MD5、HASH、字符串列作为主键无法保证数据的顺序增长。

    二级索引(辅助索引、非聚簇索引)

    上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用,因为B+树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该怎么办呢?肯定不能是从头到尾沿着链表依次遍历记录一遍。

    答案:我们可以多建几棵B+树,不同的B+树中的数据采用不同的排序规则。比方说我们用c2列的大小作为数据页、页中记录的排序规则,再建一棵B+树,效果如下图所示:

    在这里插入图片描述

    现在我们查找从c2为4(c2为非主键)的记录,先从顶部开始找,最后找到页34,页35,如下图:

    在这里插入图片描述

    现在我们知道了c2==4的三条记录,但是字段只有c1,c2,我们要查找到它的全部记录,就需要把c1字段的值拿去聚簇索引里面查找,这个过程就叫做回表

    回表

    我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值,所以如果我们想根据c2列的值查找到完整的用户记录的话,仍然需要到聚簇索引中再查一遍,这个过程称为回表。也就是根据c2列的值查询一条完整的用户记录需要使用到2棵B+树!|

    问题:为什么我们还需要一次回表操作呢?直接把完整的用户记录放到叶子节点不OK吗?

    如果把完整的用户记录放到叶子节点是可以不用回表。但是太占地方了,相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍,这就有点太浪费存储空间了。
    我们一个表中只能有一个聚簇索引,而可以有多个二级索引,这样的话我们有多个二级索引时,还需要多复制几遍所有的用户记录,占得位置大

    因为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录,所以这种B+树也被称为二级索引(英文名secondary index ),或者辅助索引。由于我们使用的是c2列的大小作为B+树的排序规则,所以我们也称这个B+树是为c2列建立的索引。

    非聚簇索引的存在不影响数据在聚簇索引中的组织,所以一张表可以有多个非聚簇索引。
    在这里插入图片描述
    小结:聚簇索引与非聚簇索引的原理不同,在使用上也有一些区别:

    • 1.聚簇索引的叶子节点存储的就是我们的数据记录,非聚簇索引的叶子节点存储的是数据位置。非聚簇索引不会影响数据表的物理存储顺序。
    • 2.一个表只能有一个聚簇索引,因为只能有一种排序存储的方式,但可以有多个非聚簇索引,也就是多个索引目录提供数据检索。
    • 3.使用聚簇索引的时候,数据的查询效率高,但如果对数据进行插入,删除,更新等操作,效率会比非聚簇索引低(这里暂时不太清楚)。

    联合索引

    我们也可以同时以多个列的大小作为排序规则,也就是同时为多个列建立索引,比方说我们想让B+树按照 c2和c3列 的大小进行排序,这个包含两层含义:

    • 先把各个记录和页按照c2列进行排序。.
    • 在记录的c2列相同的情况下,采用c3列进行排序
      在这里插入图片描述

    注意一点,以c2和c3列的大小为排序规则建立的B+树称为 联合索引 ,本质上也是一个二级索引。它的意思与分别为c2和c3列分别建立索引的表述是不同的,不同点如下:

    • 建立 联合索引 只会建立如上图一样的1棵B+树。
    • 为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。

    InnoDB的B+树索引的注意事项

    1. 根页面位置万年不动
      我们前边介绍B+树索引的时候,为了大家理解上的方便,先把存储用户记录的叶子节点都画出来,然后接着画存储目录项记录的内节点,实际上B+树的形成过程是这样的:
      1.每当为某个表创建一个B+树索引(聚簇索引不是人为创建的,默认就有)的时候,都会为这个索引创建一个根节点页面。最开始表中没有数据的时候,每个B+树索引对应的根节点中既没有用户记录,也没有目录项记录
      2.随后向表中插入用户记录时,先把用户记录存储到这个根节点中。
      3.当根节点中的可用空间用完时继续插入记录,此时会将根节点中的所有记录复制到一个新分配的页,比如页a中,然后对这个新页进行页分裂的操作,得到另一个新页,比如页b。这时新插入的记录根据键值(也就是聚簇索引中的主键值,二级索引中对应的索引列的值)的大小就会被分配到页a或者b中,而根节点便升级为存储目录项记录的页。
      这个过程特别注意的是:一个B+树索引的根节点自诞生之日起,便不会再移动。这样只要我们对某个表建立一个索引,那么它的根节点的页号便会被记录到某个地方,然后凡是InnoDB存储引擎需要用到这个索引的时候,都会从那个固定的地方取出根节点的页号,从而来访问这个索引。
    2. 内节点中目录项记录的唯一性
      我们知道B+树索引的内节点中目录项记录的内容是索引列+页号的搭配,但是这个搭配对于二级索引来说有点儿不严谨。还拿index_demo表为例,假设这个表中的数据是这样的:
      在这里插入图片描述
      如果二级索引中目录项记录的内容只是索引列+页号的搭配的话,那么为c2列建立索引后的B+树应该长这样:
      在这里插入图片描述
      如果我们想新插入一行记录,其中c1、c2、c3的值分别是:9、1、 ‘c’,那么在修改这个为c2列建立的二级索引对应的B+树时便碰到了个大问题:由于页3中存储的目录项记录是由c2列+页号的值构成的,页3中的两条目录项记录对应的c2列的值都是1,而我们新插入的这条记录的c2列的值也是1,那我们这条新插入的记录到底应该放到页4中,还是应该放到页5中啊?答案是:对不起,懵了。
      为了让新插入记录能找到自己在那个页里,我们需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的:
      索引列
      主键值
      页号
      也就是我们把主键值也添加到二级索引内节点中的目录项记录了,这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的,所以我们为c2列建立二级索引后的示意图实际上应该是这样子的:
      在这里插入图片描述
      这样我们再插入记录(9,1, ‘c’)时,由于页3中存储的目录项记录是由c2列+主键+页号的值构成的,可以先把新记录的c2列的值和页3中各目录项记录的c2列的值作比较,如果c2列的值相同的话,可以接着比较主键值,因为B+树同一层中不同目录项记录的c2列+主键的值肯定是不一样的,所以最后肯定能定位唯一的一条目录项记录,在本例中最后确定新记录应该被插入到页5中。(所以我们的二级索引在目录节点时,也有保存其主键值)
    3. 一个页面最少存储2条记录
      一个B+树只需要很少的层级就可以轻松存储数亿条记录,查询速度相当不错!这是因为B+树本质上就是一个大的多层级目录,每经过一个目录时都会过滤掉许多无效的子目录,直到最后访问到存储真实数据的目录。那如果一个大的目录中只存放一个子目录是个啥效果呢?那就是目录层级非常非常非常多,而且最后的那个存放真实数据的目录中只能存放一条记录。费了半天劲只能存放一条真实的用户记录?所以InnoDB的一个数据页至少可以存放两条记录。

    MyLSAM中的索引方案

    我们知道InnoDB中索引即数据,也就是聚簇索引的那棵B+树的叶子节点中已经把所有完整的用户记录都包含了,而MyISAM的索引方案虽然也使用树形结构,但是却将索引和数据分开存储:

    • 将表中的记录按照记录的插入顺序单独存储在一个文件中,称之为数据文件。这个文件并不划分为若干个数据页,有多少记录就往这个文件中塞多少记录就成了。由于在插入数据的时候并没有刻意按照主键大小排序,所以我们并不能在这些数据上使用二分法进行查找。
    • 使用”MyISAN存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM会单独为表的主键创建一个索引,只不过在索引的叶子节点中存储的不是完整的用户记录,而是主键值+数据记录地址的组合。
      在这里插入图片描述
      这里设表一共有三列,假设我们以col1为主键,上图是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主键索引和二级索引 (Secondary key)在结构上没有任何区别,只是主键索引要求key是唯一的,而二级索引的key可以重复。如果我们在col2上建立一个二级索引,则此索引的结构如下图所示:
      在这里插入图片描述
      同样也是一棵B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为:首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

    MylSAM与InnoDB对比

    MyISAM的索引方式都是“非聚簇”的,与InnoDB包含1个聚簇索引是不同的。小结两种引擎中索引的区别:

    1. 在InnoDB存储引擎中,我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录,而在MyISAM中,却需要进行一次回表操作,意味着MylSAM中建立的索引相当于全部都是二级索引。
    2. InnoDB的数据文件本身就是索引文件,而MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。
    3. InnoDB的非聚簇索引data域存储相应记录主键的值,而MyISAM索引记录的是地址。换句话说lnnoDB的所有非聚簇索引都引用主键作为data域。
    4. MyISAM的回表操作是十分快速的,因为是拿着地址偏移量直接到文件中取数据的,反观InnoDB是通过获取主键之后再去聚簇索引里找记录,虽然说也不慢,但还是比不上直接用地址去访问。
    5. InnoDB要求表必须有主键(_MyISAM可以没有)。如果没有显式指定,则MySQL系统会自动选择一个可以非空且唯一标识数据记录的列作为主键。如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整型。

    小结

    了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助。比如:

    1. 举例1:知道了InnoDB的索引实现后,就很容易明白为什么不建议使用过长的字段作为主键,因为所有二级索引都引用主键索引,过长的主键索引会令二级索引变得过大。
    2. 举例2:用非单调的字段作为主键在innoDB中不是个好主意,因为InnoDB数据文件本身是一棵B+Tree,非单调的主键会造成在插入新记录时,数据文件为了维持B+Tree的特性而频繁的分裂调整,十分低效,而使用自增字段作为主键则是一个很好的选择。

    在这里插入图片描述

    索引的代价

    索引是个好东西,可不能乱建,它在空间和时间上都会有消耗:

    • 空间上的代价
      每建立一个索引都要为它建立一棵B+树,每一棵B+树的每一个节点都是一个数据页,一个页默认会占用16KB的存储空间,一棵很大的B+树由许多数据页组成,那就是很大的一片存储空间。
    • 时间上的代价
      每次对表中的数据进行增、删、改操作时,都需要去修改各个B+树索引。而且我们讲过,B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录,还是内节点中的记录(也就是不论是用户记录还是目录项记录)都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏,所以存储引擎需要额外的时间进行一些记录移位,页面分裂、页面回收等操作来维护好节点和记录的排序。如果我们建了许多索引,每个索引对应的B+树都要进行相关的维护操作,会给性能拖后腿。

    一个表上索引建的越多,就会占用越多的存储空间,在增删改记录的时候性能就越差。为了能建立又好又少的索引,我们得学学这些索引在哪些条件下起作用的。

    MySQL数据结构选择的合理性

    从MysQL的角度讲,不得不考虑一个现实问题就是磁盘l0。如果我们能让索引的数据结构尽量减少硬盘的l/o操作,所消耗的时间也就越小。可以说,磁盘的 I/0操作次数对索引的使用效率至关重要。

    查找都是索引操作,一般来说索引非常大,尤其是关系型数据库,当数据量比较大的时候,索引的大小有可能几个G甚至更多,为了减少索引在内存的占用,数据库索引是存储在外部磁盘上的。当我们利用索引查询的时候,不可能把整个索引全部加载到内存,只能逐一加载,那么MySQL衡量查询效率的标准就是磁盘I0次数。

    Hash结构

    Hash本身是一个函数,又被称为散列函数,它可以帮助我们大幅提升检索数据的效率。

    Hash算法是通过某种确定性的算法(比如MD5、SHA1、SHA2、SHA3)将输入转变为输出。相同的输入永远可以得到相同的输出,假设输入内容有微小偏差,在输出中通常会有不同的结果。

    举例:如果你想要验证两个文件是否相同,那么你不需要把两份文件直接拿来比对,只需要让对方把 Hash函数计算得到的结果告诉你即可,然后在本地同样对文件进行Hash 函数的运算,最后通过比较这两个Hash 函数的结果是否相同,就可以知道这两个文件是否相同。

    加速查找速度的数据结构,常见的有两类:

    1. 树,例如平衡二叉搜索树,查询/插入/修改/删除的平均时间复杂度都是o(log2N)
    2. 哈希,例如HashMap,查询/插入/修改/删除的平均时间复杂度都是o(1)(key,value)
      在这里插入图片描述
      采用Hash进行检索效率非常高,基本上一次检索就可以找到数据,而B树需要自顶向下依次查找,多次访问节点才能找到数据,中间需要多次I/o操作,从效率来说Hash 比 B+树更快

    在哈希的方式下,一个元素k处于h(k)中,即利用哈希函数h,根据关键字k计算出槽的位置。函数h将关键字域映射到哈希表T[o…m-1]的槽位上。
    在这里插入图片描述
    上图中哈希函数h有可能将两个不同的关键字映射到相同的位置,这叫做碰撞,在数据库中一般采用链接法来解决。在链接法中,将散列到同一槽位的元素放在一个链表中,如下图所示:
    在这里插入图片描述

    Hash结构效率高,那为什么索引结构要设计成树型呢?

    1. 原因1: Hash索引仅能满足(=)(<>)和IN查询。如果进行范围查询,哈希型的索引,时间复杂度会退化为o(n);而树型的“有序”特性,依然能够保持o(log2N)的高效率。
    2. 原因2: Hash索引还有一个缺陷,数据的存储是没有顺序的,在ORDER BY的情况下,使用Hash索引还需要对数据重新排序。
    3. 原因3:对于联合索引的情况,Hash值是将联合索引键合并后一起来计算的,无法对单独的一个键或者几个索引键进行查询。
    4. 原因4∶对于等值查询来说,通常Hash索引的效率更高,不过也存在一种情况,就是索引列的重复值如果很多,效率就会降低。这是因为遇到Hash冲突时,需要遍历桶中的行指针来进行比较,找到查询的关键字,非常耗时。所以,Hash索引通常不会用到重复值多的列上,比如列为性别、年龄的情况等。

    Hash索引适用存储引擎如表所示:

    在这里插入图片描述

    Hash索引的适用性:

    1. Hash索引存在着很多限制,相比之下在数据库中B+树索引的使用面会更广,不过也有一些场景采用Hash索引效率更高,比如在键值型(Key-Value)数据库中,Redis 存储的核心就是 Hash表。
    2. MySQL中的Memory存储引擎支持Hash存储,如果我们需要用到查询的临时表时,就可以选择Memory存储引擎,把某个字段设置为Hash 索引,比如字符串类型的字段,进行Hash计算之后长度可以缩短到几个字节。当字段的重复度低,而且经常需要进行等值查询的时候,采用Hash索引是个不错的选择。
    3. 另外,InnoDB本身不支持Hash 索引,但是提供自适应 Hash索引(Adaptive Hash Index)。什么情况下才会使用自适应Hash索引呢?如果某个数据经常被访问,当满足一定条件的时候,就会将这个数据页的地址存放到Hash表中。这样下次查询的时候,就可以直接找到这个页面的所在位置。这样让B+树也具备了Hash 索引的优点。
      在这里插入图片描述
      采用自适应Hash 索引目的是方便根据SQL的查询条件加速定位到叶子节点,特别是当B+树比较深的时候,通过自适应Hash索引可以明显提高数据的检索效率。

    二叉搜索树

    如果我们利用二叉树作为索引结构,那么磁盘的Io次数和索引树的高度是相关的

    二叉搜索树的特点

    1. 一个节点只能有两个子节点,也就是一个节点度不能超过2
    2. 在子节点<本节点;右子节点>=本节点,比我大的向右,比我小的向左

    二叉搜索树也属于二分查找树,极端情况下会退化成了一条链表,查找数据的时间复杂度变成了0(n)。

    为了提高查询效率,就需要减少磁盘I0数。为了减少磁盘Io的次数,就需要尽量降低树的高度,需要把原来“瘦高”的树结构变的“矮胖”,树的每层的分叉越多越好。

    AVL树

    为了解决上面二叉查找树退化成链表的问题,人们提出了平衡二叉搜索树(Balanced Binary Tree),又称为AVL树,它在二叉搜索树的基础上增加了约束,具有以下性质:

    • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

    数据查询的时间主要依赖于磁盘I/o的次数,如果我们采用二叉树的形式,即使通过平衡二叉搜索树进行了改进,树的深度也是 o(log2n),当n比较大时,深度也是比较高的,比如下图的情况:
    在这里插入图片描述
    每访问一次节点就需要进行一次磁盘Ⅰ/О 操作,对于上面的树来说,我们需要进行5次I/O操作。虽然平衡二叉树的效率高,但是树的深度也同样高,这就意味着磁盘Ⅳ/О操作次数多,会影响整体数据查询的效率。

    针对同样的数据,如果我们把二叉树改成M叉树(M>2)呢?当M=3时,同样的31个节点可以由下面的三叉树来进行存储:
    在这里插入图片描述
    你能看到此时树的高度降低了,当数据量N大的时候,以及树的分叉数M大的时候,M叉树的高度会远小于二叉树的高度(M>2)。所以,我们需要把树从“瘦高"变“矮胖”

    B-Tree

    B树的英文是Balance Tree,也就是多路平衡查找树。简写为B-Tree(注意横杠表示这两个单词连起来的意思,不是减号)。它的高度远小于平衡二叉树的高度。
    在这里插入图片描述

    B树作为多路平衡查找树,它的每一个节点最多可以包括M个子节点,M称为B树的阶。每个磁盘块中包括了关键字和子节点的指针。如果一个磁盘块中包括了x个关键字,那么指针数就是x+1。对于一个100阶的B树来说,如果有3层的话最多可以存储约100万的索引数据。对于大量的索引数据来说,采用B树的结构是非常适合的,因为树的高度要远小于二叉树的高度。

    你能看出来在B树的搜索过程中,我们比较的次数并不少,但如果把数据读取出来然后在内存中进行比较,这个时间就是可以忽略不计的。而读取磁盘块本身需要进行I/o操作,消耗的时间比在内存中进行比较所需要的时间要多,是数据查找用时的重要因素。B树相比于平衡二叉树来说磁盘Ⅰ/0О操作要少,在数据查询中比平衡二叉树效率要高。所以只要树的高度足够低,IO次数足够少,就可以提高查询性能

    小结:

    1. B树在插入和删除节点的时候如果导致树不平衡,就通过自动调整节点的位置来保持树的自平衡
    2. 关键字集合分布在整棵树中,即吁子节点和非叶子节点都存放数据。搜索有可能在非叶子节点结束
    3. 其搜索性能等价于在关键字全集内做一次二分查找。

    B+Tree

    B+树也是一种多路搜索树,基于B树做出了改进,主流的DBMS都支持B+树的索引方式,比如MySQL。相比于B-Tree,B+Tree适合文件索引系统。

    B+树和B树的差异在于以下几点:

    1. 有k个孩子的节点就有k个关键字。也就是孩子数量=关键字数,而B树中,孩子数量=关键字数+1。
    2. 非叶子节点的关键字也会同时存在在子节点中,并且是在子节点中所有关键字的最大(或最小)。
    3. 非叶子节点仅用于索引,不保存数据记录,跟记录有关的信息都放在叶子节点中。而B树中,非叶子节点既保存索引,也保存数据记录。
    4. 所有关键字都在叶子节点出现,叶子节点构成一个有序链表,而且叶子节点本身按照关键字的大小从小到大顺序链接。

    看起来B+树和B树的查询过程差不多,但是B+树和B树有个根本的差异在于,B+树的中间节点并不直接存储数据。这样的好处都有什么呢?

    1. 首先,B+树查询效率更稳定。因为B+树每次只有访问到叶子节点才能找到对应的数据,而在B树中,非叶子节点也会存储数据,这样就会造成查询效率不稳定的情况,有时候访问到了非叶子节点就可以找到关键字,而有时需要访问到叶子节点才能找到关键字。
    2. 其次,B+树的查询效率更高。这是因为通常B+树比B树更矮胖(阶数更大,深度更低),查询所需要的磁盘I/o也会更少。同样的磁盘页大小,B+树可以存储更多的节点关键字。
    3. 不仅是对单个关键字的查询上,在查询范围上,B+树的效率也比B树高。这是因为所有关键字都出现在B+树的叶子节点中,叶子节点之间会有指针,数据又是递增的,这使得我们范围查找可以通过指针连接查找。而在B树中则需要通过中序遍历才能完成查询范围的查找,效率要低很多。

    B树和B+树都可以作为索引的数据结构,在 MySQL中采用的是B+树。
    但B树和B+树各有自己的应用场景,不能说B+树完全比B树好,反之亦然。

    思考题:为了减少Io,索引树会一次性加载吗?

    1. 数据库索引是存储在磁盘上的,如果数据量很大,必然导致索引的大小也会很大,超过几个G。
    2. 当我们利用索引查询时候,是不可能将全部几个c的索引都加载进内存的,我们能做的只能是:逐一加载每一个磁盘页,因为磁盘页对应着索引树的节点。

    思考题:B+树的存储能力如何?为何说一般查找行记录,最多只需1~3次磁盘Io

    InnoDB存储引擎中页的大小为16KB,一般表的主键类型为INT(占用4个字节)或BIGINT(占用8个字节),指针类型也一般为4或8个字节,也就是说一个页(B+Tree中的一个节点)中大概存储16KB/(8B+8B)=1K个键值(因为是估值,为方便计算,这里的K取值为103。也就是说一个深度为3的B+Tree索引可以维护103 * 103 * 103= 10亿条记录。(这里假定一个数据页也存储103条行记录数据了)
    实际情况中每个节点可能不能填充满,因此在数据库中,B+Tree 的高度一般都在2-4层。MySQL的 InnoDB存储引擎在设计时是将根节点常驻内存的,也就是说查找某一键值的行记录时最多只需要1~3次磁盘1/o操作

    思考题:为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引?

    1. B+树的磁盘读写代价更低
      B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说Io读写次数也就降低了。
    2. B+树的查询效率更加稳定
      由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当

    思考题:Hash索引与B+树索引的区别??

    我们之前讲到过B+树索引的结构,Hash索引结构和B+树的不同,因此在索引使用上也会有差别。

    1. Hash索引不能进行范围查询,而B+树可以。这是因为Hash索引指向的数据是无序的,而B+树的叶子节点是个有序的链表.
    2. Hash索引不支持联合索引的最左侧原则(即联合索引的部分索引无法使用),而B+树可以。对于联合索引来说,Hash 索引在计算Hash值的时候是将索引键合并后再一起计算Hash值,所以不会针对每个索引单独计算Hash值。因此如果用到联合索引的一个或者几个索引时,联合索引无法被利用。
    3. Hash索引不支持ORDER BY排序,因为Hash索引指向的数据是无序的,因此无法起到排序优化的作用,而B+树索引数据是有序的,可以起到对该字段ORDER BY排序优化的作用。同理,我们也无法用Hash索引进行模糊查询,而B+树使用LIKE进行模糊查询的时候,LIKE后面模糊查询(比如%结尾)的话就可以起到优化作用
    4. InnoDB不支持Hash索引

    思考题:Hash索引与B+树索引是在建索引的时候手动指定的吗?

    在这里插入图片描述
    你能看到,针对InnoDB和MyISAM存储引擎,都会默认采用B+树索引,无法使用Hash索引。InnoDB提供的自适应Hash是不需要手动指定的。如果是Memory/Heap和NDB存储引擎,是可以进行选择Hast索引的

    小结

    • 使用索引可以帮助我们从海量的数据中快速定位想要查找的数据,不过索引也存在一些不足,比如占用存储空间、降低数据库写操作的性能等,如果有多个索引还会增加索引选择的时间。当我们使用索引时,需要平衡索引的利(提升查询效率)和弊(维护索引所的代价)。
    • 在实际工作中,我们还需要基于需求和数据本身的分布情况来确定是否使用索引,尽管索引不是万能的,`但数据量大的时候不使用索引是不可想象的,毕竟索引的本质,是帮助我们提升数据检索的效率。
    展开全文
  • MySQL索引底层数据结构详解

    千次阅读 2022-03-15 11:24:09
    MySQL底层使用的是B+tree存储结构 非叶子节点存储索引和下一个子节点的地址 叶子结点存储所有的索引数据

    索引是帮助MySQL高效获取数据的排好序的数据结构

    • 索引的数据结构:

    1.二叉树 在这里插入图片描述

    通过一个简单的插入你可以看到,二叉树的插入会根据每个节点进行判断,每一个节点右边的数据一定是大于等于这个节点数据,而他的左边数据一定是小于这个节点的数据
    他的插入,删除,查找都是根据这个特性来的。
    这里我们可以看到如果我们的数据是排序依次插入,就会是一条链表,这样查询的速度可以说是超级慢,所以二叉树不适合mysql的存储

    2.红黑树

    在这里插入图片描述
    红黑树又叫做平衡二叉树,在二叉树的基础上进行了平衡的算法,他平衡的原理就依靠红和黑两个颜色的约束决定的
    1.结点是红色或者黑色
    2.根节点是黑色
    3.所有叶子都是黑色
    4.每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
    5.从任一节结点到其每个叶子的所有路径都包含相同数目的黑色结点。
    虽然红黑树做了平衡处理,但我们可以看到,如果我们的数据量特别大,达到千万,亿万级别的时候,红黑树的高度会特别的大,这样我们查询的时候其实跟链表差不多了

    3.B-tree
    在这里插入图片描述
    通过B树的插入演示,B树的度就是每个结点存储的个数,当子节点存储满足了度,就会将处于中间的那个数据往父节点存储,有以下几个特点:
    叶节点具有相同的深度
    叶节点的指针为空
    节点中的数据key从左到右递增排列
    对于B树而言,相同的一个节点可以存储多个数据,这样的话,它的高度就会得到控制。但是mysql也没有用到B树作为存储结构,我们可以看到B树他的每一个节点都存有数据,而mysql底层存储使用的是B+树,则是把这个数据都放在了叶子结点

    在这里插入图片描述

    B+tree
    在这里插入图片描述
    B+树对于B树而言又进行了优化,可以看到他的叶子结点是有一个指针指向下一份叶子结点,里面存储了下一个节点的位置信息,是为了叶子结点之间能够快速地查找,而mysql内部就是使用的这种存储模式

    MySQL底层的数据结构:
    在这里插入图片描述
    MySQL将所有的数据都放到了叶子节点中,而根节点和非叶子节点中放的都是冗余的索引Key,可以理解为我们所有的数据都是key-value的形式存放的,这些数据都是放在叶子节中(最后一行数据),而他们的父节点都是所有数据的key用算法算出中间的平衡值作为父节点,这样做有两个好处,一个是增加非叶子节点的度,还有就是减少io的磁盘消耗,下面会讲到。

    MySQL查找的实现顺序:
    1.将根节点磁盘页数据(第一行数据)load到内存中进行比较,找到要查找数据的在那个区间
    2.然后再将第二行磁盘页load到内存中,执行上面的操作,找到区间
    3. 1,2步骤的查找是相当快的, 因为他都是排好序的,消耗的内存也很少,因为他只存了key值,这就是要将数据放在叶子节点的好处,最后在叶子节点找到要查找的key,在把value一起拿出来,就查找到了我们的结果

    MySQL是怎么限制树的高度?
    MySQL底层将每一个磁盘页的大小设置为16k,可以使用 sql语句:show global status like ‘Innodb_page_size’; 这个值是mysql经过多次测试设置的,可以修改,但不建议修改,
    在这里插入图片描述
    比如我们索引使用的ID,bigint类型占用八个字节加上一个地址大约6个字节,就是16kb/8+6kb=1170个节点,最后叶子结点存放了数据就算是1k,存储的数据达到了两千多万的数据,而他的树高度只有3,就是说我们只需要三次磁盘的io就可以完成查找,还可以将根节点放到磁盘中,这样就只需要两次,速度也是相当于快。
    在这里插入图片描述
    总结一下:
    MySQL底层使用的是B+tree存储结构
    非叶子节点存储索引和下一个子节点的地址
    叶子结点存储所有的索引和数据

    展开全文
  • 第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础。 第二部分结合MySQL数据库中MyISAM和InnoDB数据存储引擎中索引的架构实现讨论聚集索引、非聚集索引及覆盖索引等话题。 第三部
  • mysql索引数据结构及原理

    千次阅读 2022-03-20 11:46:03
    mysql数据库,存储引擎,InnoDB,MyISAM,B-Tree、B+Tree、索引数据结构
  • MySql索引数据结构(BTREE和Hash)

    千次阅读 2022-03-09 14:04:28
    3、Hash 索引无法被用来避免数据的排序操作 4、Hash 索引不能利用部分索引键查询。 5、Hash 索引在任何时候都不能避免表扫描。 6、Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。 ......
  • mysql索引数据结构

    千次阅读 2020-09-02 18:09:07
    由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值,而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样,所以数据库无法利用索引数据来避免任何排序运算 3.Hash 索引不能利用部分索引键查询 对于...
  • MySQL索引数据结构与算法.pptx
  • 本文收录于JavaStarter ,里面有我完整的Java系列文章,学习或面试都可以看看哦(一)关于索引索引是帮助Mysql更加高效获取数据的一种数据结构索引的使用很简单,但是如果不能理解索引底层的数据结构的话,就谈不...
  • MySQL索引详解之索引的数据结构

    千次阅读 2020-04-21 18:53:22
    下面就以MySQL索引为对象,通过几篇文章来带大家好好的学习下索引的知识。 索引的数据结构 索引的存储方式 索引的利弊以及高效使用 什么是索引 数据库索引指的是数据库管理系统中一个排序的数据结构,以协助快速查.....
  • MySQL索引数据结构以及算法原理

    万次阅读 多人点赞 2018-04-19 22:13:28
    写在前面的话 在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构加算法),但是在日常的学习和工作中我确认深深感受到数据结构和算法的重要性,...
  • Mysql索引结构

    2021-07-21 06:52:50
    mysql索引数据结构有hash和b+tree,hash由数组和链表组成。hash不支持范围查找。 B-Tree由红黑树(从左到右为小中大)变化而来,不同的是btree一个节点里面有多个节点,并且节点含有数据。B+tree(有冗余节点)是B-...
  • 4.2.1 B树数据结构4.2.2 B+树数据结构,以及为什么选择B+树4.2.3 一个错误的观点:B树和B+树的区别之一为B树的非叶子节点存储数据4.3 简单猜想:为什么索引中每个节点在内存中的地址是随机的5 MySQL索引的体现形式...
  • 深入理解Mysql索引底层数据结构与算法

    万次阅读 多人点赞 2018-10-14 20:09:44
    索引是帮助MySQL高效获取数据的排好序的数据结构(容易忽略的点:排好序)(形象点就是教科书的目录) 索引存储在文件里(也就是说有IO操作) 索引结构: 这里说说在几种数据结构中,mysql为什么选择hash,B+...
  • mysql索引数据结构是什么

    千次阅读 2021-01-21 10:36:53
    一、简介mysql索引数据结构是树,常用的存储引擎innodb采用的是B+Tree。这里对B+Tree及其相关的查找树进行简要介绍。二、各种查找树1、二叉排序树(也称为二叉查找树)二叉排序树是最简单的查找树,特点:a)是一棵...
  • MySQL索引背后的数据结构及算法原理,帮助了解MYsql的索引和原理,高级工程师进阶的必选。。。。。
  • MySQL 高级篇 -- 索引数据结构

    千次阅读 2022-03-16 15:31:34
    索引(Index)是帮助 MySQL 高效获取数据的数据结构
  • MySQL索引的本质,MySQL索引的实现,MySQL索引数据结构
  • MySQL中的索引数据结构是 B+ 树。 B+树使用所有叶子结点作为数据页,它是一个双向链表,所有数据记录节点都是按照键值的大小存放在这里;使用非叶子结点作为索引页,记录着每页数据页的页号和该数据页中最小的主键...
  • MySQL高级篇——索引数据结构

    千次阅读 多人点赞 2022-04-11 16:35:12
    文章目录: 1.为什么使用索引? 2.索引的优缺点 3.InnoDB中的索引 3.1 设计索引 ...3.2 常见索引概念 ...MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构索引
  • mysql联合索引数据结构

    千次阅读 多人点赞 2020-08-05 16:16:53
    在分享这篇文章之前,我在网上查了关于MySQL联合索引在B+树上的存储结构这个问题,翻阅了很多博客和技术文章,其中有几篇讲述的与事实相悖。庆幸的是看到搜索引擎列出的有一条是来自思否社区的问答,有答主回答了这...
  • MySQL索引结构

    千次阅读 2021-08-20 21:56:40
    MySQL索引结构 MySQL官方对索引的定义是: 索引(index)是帮助MySQL高效获取数据的一种数据结构(有序)。在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这种数据结构以某种方式引用(指向)数据,...
  • MySQL哈希索引数据结构以及索引的优缺点

    千次阅读 多人点赞 2021-08-03 11:27:39
    MySQL哈希索引结构的实现,以及索引的优缺点。
  • mysql索引数据结构以及各自优势

    千次阅读 2022-03-27 16:22:23
    索引数据结构和具体存储引擎的实现有关,在MySQL中较多的索引有Hash索引、B+树索引等。InnoDB存储引擎的默认索引实现为:B+树索引。 对于哈希索引来说,底层的数据结构就是哈希表,因此在绝大多数需求为单条记录...
  • mysql 索引数据结构(笔记)

    千次阅读 2020-03-12 12:32:09
    索引的用途:帮助mysql高效获取数据的数据结构索引使用策略及优化: mysql优化主要分为结构优化和查询优化。 一般在数据库系统或文件系统中使用的B+Tree结构都在经典B+Tree的基础上进行了优化,增加了顺序访问...
  • MySQL索引背后的数据结构及算法原理,技术面试重要内容呀
  • MySQL中InnoDB索引数据结构(B+树)详解 参考文章:CodingLabs - MySQL索引背后的数据结构及算法原理 MySQL中常用存储引擎有哪些?它们相互之间有什么区别? - 知乎 (zhihu.com) 一、MySQL中的数据存储引擎 存储引擎...
  • Mysql索引数据结构,各⾃优劣 InnoDB存储引擎的默认索引实现为:B+树索引。 对于哈希索引来说,底层的数据结构就是哈希表,因此在绝⼤多数需求为单条记录查询的时候,可以选择哈希索引,查询性能最快;其余⼤...
  • MySQL索引结构原理分析

    千次阅读 2021-02-02 06:52:16
    这里用百度百科的一句话来说,在关系数据库中,索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 272,601
精华内容 109,040
关键字:

mysql索引数据结构

mysql 订阅
数据结构 订阅