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

    2020-03-26 12:21:07
    一步一步推导出 Mysql 索引底层数据结构。 Mysql 作为互联网中非常热门的数据库,其底层的存储引擎和数据检索引擎的设计非常重要,尤其是 Mysql 数据的存储形式以及索引的设计,决定了 Mysql 整体的数据检索性能...
    一步一步推导出 Mysql 索引的底层数据结构。

    Mysql 作为互联网中非常热门的数据库,其底层的存储引擎和数据检索引擎的设计非常重要,尤其是 Mysql 数据的存储形式以及索引的设计,决定了 Mysql 整体的数据检索性能。

    我们知道,索引的作用是做数据的快速检索,而快速检索的实现的本质是数据结构。通过不同数据结构的选择,实现各种数据快速检索。在数据库中,高效的查找算法是非常重要的,因为数据库中存储了大量数据,一个高效的索引能节省巨大的时间。比如下面这个数据表,如果 Mysql 没有实现索引算法,那么查找 id=7 这个数据,那么只能采取暴力顺序遍历查找,找到 id=7 这个数据需要比较 7 次,如果这个表存储的是 1000W 个数据,查找 id=1000W 这个数据那就要比较 1000W 次,这种速度是不能接受的。

    一、Mysql 索引底层数据结构选型

    1. 哈希表(Hash)

    哈希表是做数据快速检索的有效利器。

    哈希算法:也叫散列算法,就是把任意值(key)通过哈希函数变换为固定长度的 key 地址,通过这个地址进行具体数据的数据结构。

    考虑这个数据库表 user,表中一共有 7 个数据,我们需要检索 id=7 的数据,SQL 语法是:

    select \* from user where id=7;
    

    哈希算法首先计算存储 id=7 的数据的物理地址 addr=hash(7)=4231,而 4231 映射的物理地址是 0x77,0x77 就是 id=7 存储的额数据的物理地址,通过该独立地址可以找到对应 user_name='g'这个数据。这就是哈希算法快速检索数据的计算过程。

    但是哈希算法有个数据碰撞的问题,也就是哈希函数可能对不同的 key 会计算出同一个结果,比如 hash(7)可能跟 hash(199)计算出来的结果一样,也就是不同的 key 映射到同一个结果了,这就是碰撞问题。解决碰撞问题的一个常见处理方式就是链地址法,即用链表把碰撞的数据接连起来。计算哈希值之后,还需要检查该哈希值是否存在碰撞数据链表,有则一直遍历到链表尾,直达找到真正的 key 对应的数据为止。

    从算法时间复杂度分析来看,哈希算法时间复杂度为 O(1),检索速度非常快。比如查找 id=7 的数据,哈希索引只需要计算一次就可以获取到对应的数据,检索速度非常快。但是 Mysql 并没有采取哈希作为其底层算法,这是为什么呢?

    因为考虑到数据检索有一个常用手段就是范围查找,比如以下这个 SQL 语句:

    select \* from user where id \>3;
    

    针对以上这个语句,我们希望做的是找出 id>3 的数据,这是很典型的范围查找。如果使用哈希算法实现的索引,范围查找怎么做呢?一个简单的思路就是一次把所有数据找出来加载到内存,然后再在内存里筛选筛选目标范围内的数据。但是这个范围查找的方法也太笨重了,没有一点效率而言。

    所以,使用哈希算法实现的索引虽然可以做到快速检索数据,但是没办法做数据高效范围查找,因此哈希索引是不适合作为 Mysql 的底层索引的数据结构。

    1. 二叉查找树(BST)

    二叉查找树是一种支持数据快速查找的数据结构,如图下所示:

    二叉查找树的时间复杂度是 O(lgn),比如针对上面这个二叉树结构,我们需要计算比较 3 次就可以检索到 id=7 的数据,相对于直接遍历查询省了一半的时间,从检索效率上看来是能做到高速检索的。此外二叉树的结构能不能解决哈希索引不能提供的范围查找功能呢?

    答案是可以的。观察上面的图,二叉树的叶子节点都是按序排列的,从左到右依次升序排列,如果我们需要找 id>5 的数据,那我们取出节点为 6 的节点以及其右子树就可以了,范围查找也算是比较容易实现。

    但是普通的二叉查找树有个致命缺点:极端情况下会退化为线性链表,二分查找也会退化为遍历查找,时间复杂退化为 O(N),检索性能急剧下降。比如以下这个情况,二叉树已经极度不平衡了,已经退化为链表了,检索速度大大降低。此时检索 id=7 的数据的所需要计算的次数已经变为 7 了。

    在数据库中,数据的自增是一个很常见的形式,比如一个表的主键是 id,而主键一般默认都是自增的,如果采取二叉树这种数据结构作为索引,那上面介绍到的不平衡状态导致的线性查找的问题必然出现。因此,简单的二叉查找树存在不平衡导致的检索性能降低的问题,是不能直接用于实现 Mysql 底层索引的。

    1. AVL 树和红黑树

    二叉查找树存在不平衡问题,因此学者提出通过树节点的自动旋转和调整,让二叉树始终保持基本平衡的状态,就能保持二叉查找树的最佳查找性能了。基于这种思路的自调整平衡状态的二叉树有 AVL 树和红黑树。

    首先简单介绍红黑树,这是一颗会自动调整树形态的树结构,比如当二叉树处于一个不平衡状态时,红黑树就会自动左旋右旋节点以及节点变色,调整树的形态,使其保持基本的平衡状态(时间复杂度为 O(logn)),也就保证了查找效率不会明显减低。比如从 1 到 7 升序插入数据节点,如果是普通的二叉查找树则会退化成链表,但是红黑树则会不断调整树的形态,使其保持基本平衡状态,如下图所示。下面这个红黑树下查找 id=7 的所要比较的节点数为 4,依然保持二叉树不错的查找效率。

    红黑树拥有不错的平均查找效率,也不存在极端的 O(n)情况,那红黑树作为 Mysql 底层索引实现是否可以呢?其实红黑树也存在一些问题,观察下面这个例子。

    红黑树顺序插入 1~7 个节点,查找 id=7 时需要计算的节点数为 4。

    红黑树顺序插入 1~16 个节点,查找 id=16 需要比较的节点数为 6 次。观察一下这个树的形态,是不是当数据是顺序插入时,树的形态一直处于“右倾”的趋势呢?从根本上上看,红黑树并没有完全解决二叉查找树虽然这个“右倾”趋势远没有二叉查找树退化为线性链表那么夸张,但是数据库中的基本主键自增操作,主键一般都是数百万数千万的,如果红黑树存在这种问题,对于查找性能而言也是巨大的消耗,我们数据库不可能忍受这种无意义的等待的。

    现在考虑另一种更为严格的自平衡二叉树 AVL 树。因为 AVL 树是个绝对平衡的二叉树,因此他在调整二叉树的形态上消耗的性能会更多。

    AVL 树顺序插入 1~7 个节点,查找 id=7 所要比较节点的次数为 3。

    AVL 树顺序插入 1~16 个节点,查找 id=16 需要比较的节点数为 4。从查找效率而言,AVL 树查找的速度要高于红黑树的查找效率(AVL 树是 4 次比较,红黑树是 6 次比较)。从树的形态看来,AVL 树不存在红黑树的“右倾”问题。也就是说,大量的顺序插入不会导致查询性能的降低,这从根本上解决了红黑树的问题。

    总结一下 AVL 树的优点:

    1. 不错的查找性能(O(logn)),不存在极端的低效查找的情况。
    2. 可以实现范围查找、数据排序。

    看起来 AVL 树作为数据查找的数据结构确实很不错,但是 AVL 树并不适合做 Mysql 数据库的索引数据结构,因为考虑一下这个问题:

    数据库查询数据的瓶颈在于磁盘 IO,如果使用的是 AVL 树,我们每一个树节点只存储了一个数据,我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里,那比如查询 id=7 这个数据我们就要进行磁盘 IO 三次,这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。

    磁盘 IO 有个有个特点,就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的,我们就可以根据这个思路,我们可以在一个树节点上尽可能多地存储数据,一次磁盘 IO 就多加载点数据到内存,这就是 B 树,B+树的的设计原理了。

    1. B 树

    下面这个 B 树,每个节点限制最多存储两个 key,一个节点如果超过两个 key 就会自动分裂。比如下面这个存储了 7 个数据 B 树,只需要查询两个节点就可以知道 id=7 这数据的具体位置,也就是两次磁盘 IO 就可以查询到指定数据,优于 AVL 树。

    下面是一个存储了 16 个数据的 B 树,同样每个节点最多存储 2 个 key,查询 id=16 这个数据需要查询比较 4 个节点,也就是经过 4 次磁盘 IO。看起来查询性能与 AVL 树一样。

    但是考虑到磁盘 IO 读一个数据和读 100 个数据消耗的时间基本一致,那我们的优化思路就可以改为:尽可能在一次磁盘 IO 中多读一点数据到内存。这个直接反映到树的结构就是,每个节点能存储的 key 可以适当增加。

    当我们把单个节点限制的 key 个数设置为 6 之后,一个存储了 7 个数据的 B 树,查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。

    一个存储了 16 个数据的 B 树,查询 id=7 这个数据所要进行的磁盘 IO 为 2 次。相对于 AVL 树而言磁盘 IO 次数降低为一半。

    所以数据库索引数据结构的选型而言,B 树是一个很不错的选择。总结来说,B 树用作数据库索引有以下优点:

    1. 优秀检索速度,时间复杂度:B 树的查找性能等于 O(h*logn),其中 h 为树高,n 为每个节点关键词的个数;
    2. 尽可能少的磁盘 IO,加快了检索速度;
    3. 可以支持范围查找。
    4. B+树

    B 树和 B+树有什么不同呢?

    第一,B 树一个节点里存的是数据,而 B+树存储的是索引(地址),所以 B 树里一个节点存不了很多个数据,但是 B+树一个节点能存很多索引,B+树叶子节点存所有的数据。

    第二,B+树的叶子节点是数据阶段用了一个链表串联起来,便于范围查找。

    通过 B 树和 B+树的对比我们看出,B+树节点存储的是索引,在单个节点存储容量有限的情况下,单节点也能存储大量索引,使得整个 B+树高度降低,减少了磁盘 IO。其次,B+树的叶子节点是真正数据存储的地方,叶子节点用了链表连接起来,这个链表本身就是有序的,在数据范围查找时,更具备效率。因此 Mysql 的索引用的就是 B+树,B+树在查找效率、范围查找中都有着非常不错的性能。

    二、Innodb 引擎和 Myisam 引擎的实现

    Mysql 底层数据引擎以插件形式设计,最常见的是 Innodb 引擎和 Myisam 引擎,用户可以根据个人需求选择不同的引擎作为 Mysql 数据表的底层引擎。我们刚分析了,B+树作为 Mysql 的索引的数据结构非常合适,但是数据和索引到底怎么组织起来也是需要一番设计,设计理念的不同也导致了 Innodb 和 Myisam 的出现,各自呈现独特的性能。

    MyISAM 虽然数据查找性能极佳,但是不支持事务处理。Innodb 最大的特色就是支持了 ACID 兼容的事务功能,而且他支持行级锁。Mysql 建立表的时候就可以指定引擎,比如下面的例子,就是分别指定了 Myisam 和 Innodb 作为 user 表和 user2 表的数据引擎。

    执行这两个指令后,系统出现了以下的文件,说明这两个引擎数据和索引的组织方式是不一样的。

    Innodb 创建表后生成的文件有:

    • frm:创建表的语句
    • idb:表里面的数据+索引文件

    Myisam 创建表后生成的文件有

    • frm:创建表的语句
    • MYD:表里面的数据文件(myisam data)
    • MYI:表里面的索引文件(myisam index)

    从生成的文件看来,这两个引擎底层数据和索引的组织方式并不一样,MyISAM 引擎把数据和索引分开了,一人一个文件,这叫做非聚集索引方式;Innodb 引擎把数据和索引放在同一个文件里了,这叫做聚集索引方式。下面将从底层实现角度分析这两个引擎是怎么依靠 B+树这个数据结构来组织引擎实现的。

    1. MyISAM 引擎的底层实现(非聚集索引方式)

    MyISAM 用的是非聚集索引方式,即数据和索引落在不同的两个文件上。MyISAM 在建表时以主键作为 KEY 来建立主索引 B+树,树的叶子节点存的是对应数据的物理地址。我们拿到这个物理地址后,就可以到 MyISAM 数据文件中直接定位到具体的数据记录了。

    当我们为某个字段添加索引时,我们同样会生成对应字段的索引树,该字段的索引树的叶子节点同样是记录了对应数据的物理地址,然后也是拿着这个物理地址去数据文件里定位到具体的数据记录。

    1. Innodb 引擎的底层实现(聚集索引方式)

    InnoDB 是聚集索引方式,因此数据和索引都存储在同一个文件里。首先 InnoDB 会根据主键 ID 作为 KEY 建立索引 B+树,如左下图所示,而 B+树的叶子节点存储的是主键 ID 对应的数据,比如在执行 select * from user_info where id=15 这个语句时,InnoDB 就会查询这颗主键 ID 索引 B+树,找到对应的 user_name='Bob'。

    这是建表的时候 InnoDB 就会自动建立好主键 ID 索引树,这也是为什么 Mysql 在建表时要求必须指定主键的原因。当我们为表里某个字段加索引时 InnoDB 会怎么建立索引树呢?比如我们要给 user_name 这个字段加索引,那么 InnoDB 就会建立 user_name 索引 B+树,节点里存的是 user_name 这个 KEY,叶子节点存储的数据的是主键 KEY。注意,叶子存储的是主键 KEY!拿到主键 KEY 后,InnoDB 才会去主键索引树里根据刚在 user_name 索引树找到的主键 KEY 查找到对应的数据。

    问题来了,为什么 InnoDB 只在主键索引树的叶子节点存储了具体数据,但是其他索引树却不存具体数据呢,而要多此一举先找到主键,再在主键索引树找到对应的数据呢?

    其实很简单,因为 InnoDB 需要节省存储空间。一个表里可能有很多个索引,InnoDB 都会给每个加了索引的字段生成索引树,如果每个字段的索引树都存储了具体数据,那么这个表的索引数据文件就变得非常巨大(数据极度冗余了)。从节约磁盘空间的角度来说,真的没有必要每个字段索引树都存具体数据,通过这种看似“多此一举”的步骤,在牺牲较少查询的性能下节省了巨大的磁盘空间,这是非常有值得的。

    在进行 InnoDB 和 MyISAM 特点对比时谈到,MyISAM 查询性能更好,从上面索引文件数据文件的设计来看也可以看出原因:MyISAM 直接找到物理地址后就可以直接定位到数据记录,但是 InnoDB 查询到叶子节点后,还需要再查询一次主键索引树,才可以定位到具体数据。等于 MyISAM 一步就查到了数据,但是 InnoDB 要两步,那当然 MyISAM 查询性能更高。

    本文首先探讨了哪种数据结构更适合作为 Mysql 底层索引的实现,然后再介绍了 Mysql 两种经典数据引擎 MyISAM 和 InnoDB 的底层实现。最后再总结一下什么时候需要给你的表里的字段加索引吧:

    1. 较频繁的作为查询条件的字段应该创建索引;
    2. 唯一性太差的字段不适合单独创建索引,即使该字段频繁作为查询条件;
    3. 更新非常频繁的字段不适合创建索引。
    展开全文
  • Mysql索引底层原理

    2020-07-19 00:03:05
    Mysql索引MySQL索引的建立对于MySQL的高效运行是很重要的,**== 索引可以大大提高MySQL的检索速度 == **。索引分为:单列索引和组合索引 单列索引,即一个索引只包含单个列,一个表可以有多个单列索引,但这不是...

    索引的本质:

    什么是索引
    mysql官方定义,索引是帮助Mysql高效获取数据的排好序的快速查找的数据结构
    即索引可以大大提高MySQL的检索速度 。

    索引的优势

    1,通过索引可以提高数据的检索效率,降低数据库的IO成本
    2,通过索引列对数据进行排序,降低数据排序的成本,降低了CPU的消耗

    索引的劣势

    1, 实际上,索引也是一张表,该表保存了主键与索引字段,并指向实体表的记录,因此建立索引会占用磁盘空间
    2,虽然索引大大提高了查询速度,同时却会降低更新表的速度,如对表进行INSERT、UPDATE和DELETE。因为更新表时,MySQL不仅要保存数据,还要保存一下索引文件。每次更新添加了索引列的字段,都会调整因为更新所带来的键值变化后的索引信息。
    3,索引只是调高效率的一个因素,如果你的mysql有大量的表,就需要花时间研究建立最优秀的索引,或优化查询。

    索引的分类

    单值索引:即一个索引只包含单个列,一个表可以有多个单列索引(但这种情况可不是复合索引)。
    唯一索引:索引列的值必须唯一,但允许有空值。
    复合索引:即一个索引包含多个列。

    基本语法
    column写一个就是单值索引,写多个就是复合索引。带UNIQUE就是唯一索引
    创建:CREATE [UNIQUE] INDEX indexName ON tableName(columnName(length));
    ALTER tableName ADD [UNIQUE] INDEX [indexName] ON (columnName(length));
    删除:DROP INDEX [indexName] ON tableName;
    查看:SHOW INDEX FROM tableName;
    只用ALTER命令
    在这里插入图片描述

    索引的数据结构

    二叉树
    红黑树
    Hash表
    B-Tree
    == 二叉树–>红黑树–>B树–>B+树(不断改进的过程)==

    二叉树:即二叉查找树:左节点小于父节点,右节点大于父节点。
    红黑树: 是一种自平衡二叉查找树,就是特化的平衡二叉树,就是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能,但它的左右子树高差有可能大于 1,所以红黑树不是严格意义上的平衡二叉树。它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除。
    性质1. 节点是红色或黑色。
    性质2. 根节点是黑色。
    性质3.所有叶子都是黑色。(叶子是NULL节点)
    性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    性质5… 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
    == 这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。*==

    BTree(多路搜索树)
    在这里插入图片描述

    B+树(多路平衡查找树)
    每个节点横向上存储多个索引元素
    叶节点存储所有的索引和数据
    在这里插入图片描述

    Mysql具体是怎么运用B+树来存储索引呢?

    存储引擎:Myisam和InnoDB
    存储引擎是形容表级别的,所以每张表的存储引擎可能不同。
    在这里插入图片描述
    MyISAM引擎 索引文件和数据文件是分离的(非聚集)
    .frm是表结构文件
    .MYD存放的是表数据
    .MYI存放表索引

    InnoDB引擎 (聚集):
    表数据文件本身就是按B+Tree组织的一个索引结构文件
    聚集索引-叶节点包含了完整的数据记录(索引值+数据)
    为什么InnoDB表必须有主键,并且推荐整型的自增主键?
    为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间)
    .frm存放表结构
    .idb存放表的索引和数据

    MyISAM存储引擎索引实现
    假设执行一个查询语句: select * from table where Col1=49;
    1,首先先去MYI文件找到索引49(MYI文件里索引的组织形式就是B+树)
    2,然后根据找到的data地址直接去MYD文件定位到相应数据
    在这里插入图片描述
    InnoDB存储引擎索引实现:

    在这里插入图片描述
    再来说说,为什么InnoDB表必须有主键,并且推荐整型的自增主键?
    因为mysql表数据文件本身就是按B+Tree组织的一个索引结构文件,它要求你必须要有主键,如果没有主键这个表数据是没办法组织的。
    (那么有同学就会说哥们你这么说我就不同意了,我之前建了InnoDB的表就没设置主键也建成功了啊!)
    那是为什么我告诉你,你没有设主键并不代表它没有主键,在mysql你建了一张表没有设主键,它会选择你可以唯一标识一条记录的那一列自动为你建一个主键,如果没有唯一标识的那一列,它会在表里面默认给你加一列,由它来帮你维护这唯一的主键索引,你是看不到的。== 说白了它必须要有这么一列主键,来帮你组织整张表的数据。所以InnoDB必须要有主键,因为它设计如此。==
    为什么推荐使用整型自增主键,而不是像UUID这样的字符串,因为它在B+树上查找索引时,要不断地进行比较,那么你认为是比较整型数快还是字符串快?更何况整型数也比较节省空间。
    为什么推荐自增?
    因为B+树所有叶节点都会通过指针串起来的,从下图可以看出B+树的一个特性:它每个节点内部都是按照递增的顺序维护的,每个节点间也是按照从左到右递增的顺序维护的。 这就是B+树的一个特性== 每个节点都是按照从左到右递增的顺序来存储。==
    在这里插入图片描述
    再来说,mysql表的所有方法并不一定非要按照B+树来,例如上述所说的它可以有很多种,Hash结构就是其一。Hash结构大概就是这么回事:
    它将索引和数据用Hash表来存储,即为每个索引建立唯一的hash值放在hash表里,对应后面跟其数据。
    比方说,我们 select from table where Col1=20;
    它会首先做一个hash运算 hash(20)=(唯一的散列值)即hash值,然后拿这个hash值去hash表里直接定位到相应的数据。
    (估计有同学又会说了,这hash索引好像更牛逼一点啊,只进行了一次hash运行就能迅速定位到数据,而且hash运算又是非常快的)
    但是,工作中99.9%以上情况都是用B+树,而不是hash。虽然感觉hash定位的效率更高。为什么?
    假如这样,select * from table where Col1>20;查找大于20 的记录。hash只能定位确定的索引,是不是对范围查找hash就没辙了。这就是hash查找的缺点,对范围查找支持的非常差。
    == 而B+树就很好的支撑范围查找了,因为B+树叶节点之间有指针,又要求了索引是自增的,所以查找大于20 的记录的时候,找到值为20的索引,接着就简单了,直接顺藤摸瓜把20 之后的节点全部拿出来就好了。==
    B树呢?由于B树叶节点是没有指针把它们穿起来的,所以当B树进行范围查找时,不能进行节点间的访问,访问到20后,要返回到父节点,从父节点向下再去访问相邻节点49,依次进行返回访问返回访问…
    在这里插入图片描述
    所以是不是觉得还是B+树更牛逼些!

    哪些情况需要创建索引呢?

    1,主键自动建立唯一索引
    2,频繁作为查询条件的字段应该创建索引
    3,查询中与其它关联的字段,外键关系建立索引
    4,频繁更新的字段不适合创建索引
    5, where条件里用不到的字段不创建索引
    6,单键/组合索引的选择问题,who?(在高并发下创建组合索引)
    7,查询中排序的字段,排序字段若通过索引去访问将大大提高排序速度。
    8,查询中统计或者分组字段

    哪些情况不要创建索引呢?

    1,表记录太少
    2,经常增删改的表
    3,如果某个数据列包含许多重复的内容,为它建立索引就没有太大实际效果

    性能分析

    Explain
    是什么?
    在这里插入图片描述
    能干嘛?
    在这里插入图片描述

    怎么用?
    explain select * from table;
    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    一般来说,得保证查询至少到达range级别,最好能到达ref。
    说说这些类型都是什么意思
    在这里插入图片描述

    展开全文
  • MySQL索引底层原理

    2020-05-21 18:44:28
    Mysql索引底层数据结构选型 1、哈希表(Hash) 通过Hash算法,能快速检索数据 数据碰撞问题用链地址法 无法进行范围搜索 2、二叉查找树(BST) 解决哈希索引无法范围搜索的问题 极端情况下会退化成线性链表,...

    Mysql索引底层数据结构选型

    1、哈希表(Hash)

    通过Hash算法,能快速检索数据

    数据碰撞问题用链地址法

    无法进行范围搜索

    2、二叉查找树(BST)

    解决哈希索引无法范围搜索的问题

    极端情况下会退化成线性链表,自增主键必然会导致极端情况

    3、红黑树

    会自动调整树形态,使其保持平衡,调整会消耗性能

    无法完全解决二叉查找树的问题

    4、AVL树

    绝对平衡的二叉树,更耗性能

    根本解决了红黑数的问题

    由于一个节点只存储一个数据,在磁盘IO上消耗过多时间

    5、B树

    由于从磁盘读取1B数据和1KB数据的时间基本一致

    因此可以在一个节点上存储多个数据,这就是B树

    即便如何,每个节点上存储的数据还是有限的

    6、B+树

    B树节点上存储的是数据,每个节点存不了很多数据

    B+树节点上存储的是索引,叶子节点上存所有的数据

    相对B树,B+树的高度降低了,减少了磁盘IO

     

    Mysql的索引用的就是B+树

    Innodb引擎和MyISAM引擎的实现

    MyISAM Innodb
    不支持事务 支持事务
    表锁 行级锁

    数据和索引分开

    (非聚集索引)

    数据和索引放一起

    (聚集索引)

    索引树的叶子节点存储数据的物理地址

    只在主键索引树的叶子节点存储具体数据,其他索引树的叶子节点存储主键。

    当使用其他索引时,先在其他索引树中找到主键,再去主键索引树中找到具体数据。这样做是为了节省空间,避免每个索引树都保存数据(聚集索引),所以性能比MyISAM差点

     

    展开全文
  • MySql索引底层原理

    2020-05-09 00:10:50
    其实,索引是帮助MySql高效获取数据的排好序的数据结构。我们先讲讲数据结构。 二、索引数据结构 2.1 Hash表 Hash索引(hash index)基于哈希表实现,对于每一行数据,存储引擎都会对所有的索引列计算一个hash码...

    一、索引

           说到索引,大家理解的肯定是把它当做字典的偏旁或者一本书的目录页,更好的指引我们找到内容。可以去这样理解,但这样太表面了。 其实,索引是帮助MySql高效获取数据的排好序数据结构。(如果没有索引则需要一条一条挨个磁盘IO查找)。我们先讲讲数据结构。

    二、索引数据结构

    2.1 Hash表

           Hash索引(hash index)基于哈希表实现,对于每一行数据,存储引擎都会对所有的索引列计算一个hash码(hash code),哈希码是一个较小的值,哈希索引将所有的哈希码存储在索引中,同时在哈希表中保存指向每个数据行的指针。如果hash码一样则会采用链表的形式存储,类似于HashMap,Hash索引适用于精准查询。

    假如有以下表:


    如果我们在name列建立索引,name数据库会使用哈希算法计算name列每一行数据的hash值并进行存储。因为Hash值是随机计算的,所以可能存在冲突,假如计算结果如下:

    我们有一条SELECT id,name,age FROM t_user WHERE name=‘石小添’; 这样的一条SQL可以直接对石小添 按哈希算法算出来一个Hash值,通过该值找到对应的记录指针,通过记录指针找到表中的哪一行数据,最后比较name是否为石小添,以保证就是要查找的行。
    但是如果我们有 SELECT id,name,age FROM t_user WHERE name>‘石小添’; 这样的一条SQL则无能为力,因为Hash表支持快速的精确查询,但是不支持范围查询。
     

    2.1 二叉树

    二叉树基本特点:逐条插入数据时,左边的子节点小于父节点,右边的子节点大于父节点,这就是排序。

    假设有一张表如上图有两个字段,当前这张表没有索引。如果我们执行一条Sql select * from table where Col2 = 89;它是要从上往下依次查询6次才能找到结果。如果在Col2字段建立索引,将该字段值用二叉树存储,那我们只需要查询2次即可得到结果。每个节点存的值类似于(key,value),key:该索引字段的值。value:该字段所在行数据存在磁盘上文件地址指针。 但是,如果我们拿字段Col1(单边增长)作为索引,一个一个逐渐插入数据(如果有索引,先维护好索引结构再插入数据)时,其得到的结果是这样的:

    这时你就会发现成了链表结构,该索引就毫无意义了,跟未建立索引查询次数是一样的。所以,Mysql索引是没有使用二叉树这种数据结构的。

    2.2 红黑树(二叉平衡树)

    红黑数又叫二叉平衡树。红黑树就很好解决了上面二叉树这种存储单边增长数据出现的情况,当逐条插入时底层的算法会自动平衡,上述Col1字段逐条插入后结果是这样的:

    这时候执行 select * from table where Col1 = 6 就只要执行3次,这种情况下的索引,查询性能上比二叉树更加优化了。但是,如果数据量非常庞大,有五百万条,2^n=五百万。n为红黑树高度,而你需要查找的数据刚好在最下面的叶子节点,那效率可想而知。所以MySql索引也没有用这种结构存储索引。

    2.3 B-Tree(B树)

    data可理解为:该索引字段所在行数据存在磁盘上文件地址指针(Myisam引擎) 或 该索引字段所在行所有字段数据。

    B-Tree特点:

    1,叶节点具有相同深度,叶节点指针为空

    2,所有索引元素不重复

    3,节点中的数据索引从左到右递增排列

    4,也满足左边的子节点小于父节点,右边的子节点大于父节点(排序)

    B-Tree结构就解决了红黑树问题,横向扩展,能存储更多的数据,就能控制好树的高度。Mysql索引就是利用B-Tree数据结构,稍微改造了下成为B+Tree。

    2.4 B+Tree(Mysql索引所用的数据结构)

    B+Tree是由B-Tree改变而来,其结构是这样的:

    B+Tree特点:

    1,非叶子节点不存储data,只存储索引(冗余),这样可以放更多的索引

    2,叶子节点包含所有索引字段

    3,叶子节点用指针连接,提高区间访问的性能

    4,也满足左边的子节点小于父节点,右边的子节点大于父节点(排序)

    总结:相对于B-Tree。B+Tree,叶子节点存储了完整的索引,而非叶子节点只存储了索引(没存data),而且索引还是有重复的,这样做的目的是为了一个节点上存储更多索引。

    为什么B+Tree非叶子结点不存data,只存索引(冗余)?

    因为MySql在设计的时候,每个节点存储大小为16KB,可以通过语句 SHOW GLOBAL STATUS LIKE 'InnoDb_page_size 查询

    假设我们用一个bigint类型的作为索引,接下来我们分析下:

    一个bigint类型占8个字节,旁边的为指向下一个节点的指针地址值,MySql底层设计为6B左右以内,这一个索引占14B,

    根节点就能存储16KB/14B=1170个索引,假设我们树的高度为3,则一共能存储 1170*1170*16条数据,这相对于B-Tree来说,在相同高度下,明显存储的数据多得多,这样做性能也明显提高了,mysql中用的B+Tree结构叶子节点是双向链表且头尾也存有互相指向对方的指针,这些指针的存在大大增加了查找性能(比如范围查找,排序查找)。

    三、常用MySqly存储引擎

    3.1 Myisam存储引擎索引实现

    3.1.1 创建一个 Myisam存储引擎 表

    CREATE TABLE `tb_myisam` (
      `id` int(11) NOT NULL,
      `col1` varchar(255) DEFAULT NULL,
      `col2` varchar(255) DEFAULT NULL,
      PRIMARY KEY (`id`)
    ) ENGINE=MyISAM DEFAULT CHARSET=utf8;

    大家都知道,数据库中数据是存在磁盘上的,tb_myisam表在磁盘上对应了三个文件:

    一个myisam表创建之后在磁盘上会有三个文件frmMYDMYI维护:
    frm:存储表结构
    MYD:存储表数据
    MYI:存储表中索引

    非聚集索引:索引和数据分开两个文件存储

    3.1.2 Myisam索引维护:

    主键索引

    Col1是主键,在Col1上建立索引。如果现在执行语句:select * from table where Col1=49;从根节点开始找,右子节点>=父节点。Myisam引擎data存储的是 该索引字段所在行数据存在磁盘上文件地址指针,就这样快速找到数据。

    非主键索引和主键索引差不多

    3.2 InnoDB存储引擎索引实现(MySql默认)

    3.2.1 创建一个 InnoDB存储引擎 表

    CREATE TABLE `tb_innodb` (
      `id` int(11) NOT NULL,
      `col1` varchar(255) DEFAULT NULL,
      `col2` varchar(255) DEFAULT NULL,
      PRIMARY KEY (`id`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
    

    InnoDB是MySql默认存储引擎,tb_InnoDB表在磁盘上对应了两个文件:

    一个InnoDB表创建之后在磁盘上会有两个文件frmibd维护:
    frm:存储表结构
    ibd:存储表索引和数据

    聚集索引:索引和数据存在同一个文件

    3.2.2 InnoDB索引维护(主键索引):我们在插入数据之前需要对索引维护之后才能插入成功

    InnoDB存储引擎索引特点:

    1,表数据文件本身就是按B+Tree组织的一个索引结构文件

    2,InnoDB索引也叫聚集索引(索引和数据存在一个文件),都存在存在tb_innodb.ibd文件,查询数据是只要过滤tb_innodb.ibd一个文件,其效率高于Myisam存储引擎。

    3,InnoDB索引叶节点包含了完整的数据记录

    4,为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?

    因为Mysql在设计时 表数据文件本身就是按B+Tree组织的一个索引结构文件,如果没有主键这个数据文件是组织不起来的。如果在建InnoDB表时没给主键,系统会自动从表字段选择一个唯一值的作为主键,如果没有,系统默认加一列(Rowid)作为主键,但我们是看不到的。那为什么推荐使用整型的自增主键呢?因为我们在用索引查数据时,会从根节点往下找,要比较左右节点的大小,很明显整型的比较效率要高于字符串(因为字符串在比较时还要先转换成ACSii码),这样效率高得多。而且整型所占空间较小,节约空间。自增主键是为了在插入数据时更好的维护索引,不用大范围改变索引数据结构(B+Tree节点都是逐渐递增的,如果当前节点已经存满16KB,则会结构发生很大改变,会有性能开销)。如果索引是逐渐递增的插入,则不会发生这种情况。

    3.2.3  InnoDB非主键索引

    可以看到叶子节点存的是表主键的值,为什么这样设计呢?一致性(如果也跟主键索引一样存储整行字段的值的话我们就需要考虑到数据的一致性了)和节省空间(没必要存两份浪费空间)

    四、联合索引(非主键索引)

    我们在开发项目时一般不创建单列索引,而是多个键创建联合索引.

    假设我们联合索引为(col1,col2,col3),分别为上图绿色方格中的三行数据,分别根据col1,col2,col3三列排序,紫色为其他非索引字段。

    原理:先根据col1排序从左往右逐渐自增。col1相同拿col2排序,依次类推。

    如果有三条语句如下:

    (1) select * from table where col1=10003 and col2=Staff;

    (2) select * from table where col2=Engineer and col3=1996-08-03;

    (3) select * from table where  col3=1996-08-03;

    根据上面讲述的排序原理我们可以知道,只有第(1)才会走索引查询,(2)(3)是不会的,这样(1)的效率明显高于(2)(3)。这就是我们常常在网上看到的最左前缀法则,建立的索引会失效。

     

     

    展开全文
  • mysql索引底层原理

    2019-09-03 23:20:56
    1 概念:索引MySQL中也叫是一种“键”,是存储引擎用于快速找到记录的一种数据结构。 2 原理及分类: 索引的目的在于提高查询效率,与我们查阅图书所用的目录是一个道理: 先定位到章,然后定位到该章下的一...
  • mysql 索引底层原理

    2019-12-26 16:47:11
    索引是帮助MySQL高效获取数据的排好序的数据结构 索引存储在文件里,存在相应的磁盘里。下面介绍InnoDB引擎 索引结构 二叉树(红黑树) hash BTREE 二叉树的性质 二叉树https://www.cs.usfca.edu/~galles/...
  • mysql索引底层原理分析
  • 深入理解 MySQL 索引底层原理 Mysql 作为互联网中非常热门的数据库,其底层的存储引擎和数据检索引擎的设计非常重要,尤其是 Mysql 数据的存储形式以及索引的设计,决定了 Mysql 整体的数据检索性能。 何为索引 我们...

空空如也

空空如也

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

mysql索引底层原理

mysql 订阅