精华内容
下载资源
问答
  • mysql底层数据结构与算法

    千次阅读 2021-03-16 17:29:26
    mysql为什么要合理使用数据结构? 索引数据结构选型: 二叉树 红黑树 hash(mysql可选择此结构): B-Tree: B+Tree(B-Tree变种,mysql默认): 数据结构在线演示 myisam的数据结构 innerDB数据结构 ...

    目录

    mysql为什么要合理使用数据结构?

    索引数据结构选型:

        二叉树

        红黑树

        hash(mysql可选择此结构):

        B-Tree:

        B+Tree(B-Tree变种,mysql默认):

       数据结构在线演示

    myisam的数据结构

    innerDB数据结构

    联合索引底层结构


    mysql为什么要合理使用数据结构?

        数据存储在mysql数据库磁盘位置是无序的,是不均匀分布的,为了解决持续的io流消耗问题,就必须使用合理的数据结构

     

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

     

    索引数据结构选型:

          mysql默认使用B+Tree,5.5版本之前使用B-Tree

        二叉树

                定义:每个结点不超过2有序树,是每个节点最多有两个子树的树结构。顶上的叫根结点,两边被称作左子树右子树

    二叉树结构图

                为什么mysql不使用二叉树?

                      像如上二叉树结构图,插入多条记录,右边会单边增加根节点,树的高度增加,查询减慢,不使用,比如主键

        红黑树

               定义:本身就是一种特殊二叉树,每个节点上都有存储位表示节点的颜色,可以是red或black

               约束:每个节点是黑色或者红色,根节点为黑色,叶子节点(特指空节点)是黑色,每个红色节点的子节点都是黑色的,任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

               特点:速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多余二倍

    红黑树结构图

              为什么mysql不使用红黑树?

                   当mysql数据量很大时,增加一条记录,数据需要平衡一次,非常消耗性能

        hash(mysql可选择此结构):

             对于索引key进行一次hash计算就可以定位出数据存储的位置,有时候B+Tree索引更加高效,仅能满足 '=','in',不支持范围查询会出现hash冲突问题

             hash值:是一个十进制的整数,有系统随机给出(对象的地址值,是一个逻辑地址,是模拟出来得到地址,不是数据实际存储的物理地址)

    hash数据结构

        B-Tree:

                叶节点的指针可以为空,所有索引元素不重复,节点中的数据索引从左到右递增排列

    B-Tree数据结构

               为什么mysql选择B+tree而不选择B-tree?

                B树每个节点都存放了真实的数据,mysql一个根节点数据存储为16KB,会导致每一个节点存储的数据量变小,所以B树的高度会变高,维护的代价大,查询修改性能会越来越低

        B+Tree(B-Tree变种,mysql默认):

                B+Tree特点:非叶子节点不存储data,只存储索引(冗余),可有存放更多的节点,叶子节点包含了所有索引字段,所有的数据都存放在叶子节点上,叶子节点使用指针访问,提升区间访问性能,从左至右递增

               mysql对B-Tree做了优化,叶子节点使用双向指针

               

    B+Tree数据结构

                mysql使用b+树根节点存储大点的bigint数据则需要8个字节,以及地址mysql中需要6个字节,一个根节点数据存储16KB数据一个节点大概能存放16 *(8 + 6)= 1170个元素,叶子节点存放16KB数据,假设一个数据1KB,那么高度为3就可以存放1170 * 1170 * 16 = 21902400个数据

     

    数据结构在线演示

               在线演示连接:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

    我们都知道mysql的数据存储引擎包含了myisam,innerdb,csv等,常用的是myisam,innerdb

     

    myisam的数据结构

               主要特点,myISAM索引文件和数据文件是分离的(非聚集)

              MyISAM 存储引擎的一个表有3个文件:  *.frm 文件存储的表的结构; *.MYD 文件存储表的数据; *.MYI 文件存储表中的索引数据;

              MYISAM 存储引擎的主键索引 和 非主键索引的存储是差不多的

    myisam引擎数据结构图

    innerDB数据结构

                   innerDB主键索引叶节点包含了完整的数据记录,二级索引的叶子节点存储主键,对应主键索引的根节点

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

                  innerdb 如果一张表中没有主键,则会选择一列不是相等的一列作为主键,如果存在相等的一列,则会自己建立新的一列帮你维护整张表的数据,如果不建立主键,就会消耗资源

    如果不是自增的,插入一个中间大小的数据,会将部分叶节点和根节点进行排序,如果是自增的,则会在最后叶节点插入数据。根节点改变的反而小

            为什么非主键索引结构叶子节点存储的是主键值?

                  数据的一致性,节省存储空间

                innerDB主键索引:

    innerDB主键索引数据结构图

     

                 innerDB非主键索引:

    innerDb二级索引数据结构图

     

    联合索引底层结构

              联合索引根据建表的先后顺序先后建立索引排序顺序,比较相等时,先比较第一列的值,如果相等,再继续比较第二列,以此类推。

              联合索引的索引字段中有一个值为null,则将其放在叶子节点的最前面;可以认为null值是最小的。

              我之前面试被问到name,age,position建立了索引,单独使用会起作用吗?联想到MongoDB索引会,觉得会,就说会了,其实是只有name会使用到,其他的单独不会使用到索引

              mysql联合索引的作用范围?

                    使用联合索引时,索引列的定义顺序将会影响到最终查询时索引的使用情况。例如联合索引(a,b,c),mysql会从最左边的列优先匹配,如果最左边的带头大哥没有使用到,在未使用覆盖索引的情况下,就只能全表扫描,如果遇到 > < between等这样的范围查询,那B+树中也就无法对下一列进行等值匹配了,注意字符串也必须使用单引号做判断,否则也无法作比较

    联合索引结构图

    下一篇explain详解

     

    展开全文
  • MySQL索引底层数据结构索引到底是什么联合索引结构MyISAM索引文件和数据文件是分离的主键索引普通索引InnoDB索引实现主键索引普通索引 索引到底是什么 索引是帮助MySQL高效获取数据的 排好序 的 数据结构 索引存储...

    索引到底是什么

    • 索引是帮助MySQL高效获取数据的 排好序数据结构
    • 索引存储在文件,MySQL使用的数据结构为 B+Tree
      在这里插入图片描述

    数据结构教学网站:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
    B-Tree 数据结构:https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653190965&idx=1&sn=53f78fa037386f85531832cd5322d2a0&chksm=8c9909efbbee80f90512f0c36356c31cc74c388c46388dc2317d43c8f8597298f233ca9c29e9&scene=21#wechat_redirect
    B+Tree 数据结构:https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653191027&idx=1&sn=4ba22e3ec8bd149f69fc0aba72e4347e&chksm=8c9909a9bbee80bfa1d8497ff0525df130414c1731b5aa5287bf16ea1cf86c8d8e6f20782184&scene=21#wechat_redirect

    联合索引结构

    在这里插入图片描述

    聚集索引和非聚集索引

    根本区别

    • 数据的物理存放顺序与索引顺序是否一致

    MyISAM和InnoDB的索引

    • MyISAM的B+Tree的叶子节点上的data,并不是数据本身,而是数据存放的地址。主索引和辅助索引没啥区别,只是主索引中的key一定得是唯一的。这里的索引都是非聚集索引。

    • InnoDB的数据文件本身就是索引文件,B+Tree的叶子节点上的data就是数据本身,key为主键,这是聚集索引。非聚集索引,叶子节点上的data是物理地址(所以聚集索引的key,不能过长)。为什么存放的主键,而不是记录所在地址呢,理由相当简单,因为记录所在地址并不能保证一定不会变,但主键可以保证。

    • 至于为什么主键通常建议使用自增id呢?

    MyISAM索引文件和数据文件是分离的(非聚集)

    主键索引

    在这里插入图片描述

    普通索引

    在这里插入图片描述

    InnoDB索引实现(聚集)

    主键索引

    在这里插入图片描述

    普通索引

    在这里插入图片描述

    1. 数据文件本身就是按B+Tree组织的一个索引结构文件
    2. 索引-叶子节点包含了完整的数据记录
    3. 为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?
    4. 为什么非主键索引结构叶子节点存储的是主键值?(一致性和节省存储空间)
    展开全文
  • MySQL - 剖析MySQL索引底层数据结构

    千次阅读 2020-07-18 16:51:14
    文章目录Pre Pre 什么是索引? 通俗的说就是为了提高效率专门设计的一种 排好序的数据结构。 怎么理解呢? 举个例子哈 如上数据 ,假设有个SQL select * from t where col2 = 22 ;

    在这里插入图片描述

    更多干货

    带你搞定MySQL实战,轻松对应海量业务处理及高并发需求,从容应对大场面试


    Pre

    什么是索引?

    通俗的说就是为了提高效率专门设计的一种 排好序数据结构

    怎么理解呢?

    举个例子哈

    在这里插入图片描述

    如上数据 ,假设有个SQL

    select *  from t where  col2 = 22 ;
    

    如果没有索引的话,是不是得逐行进行全表扫描,走磁盘IO…

    如果加上一个合适的索引呢?

    比如用一个二叉树

    在这里插入图片描述

    二叉树我们知道,右边的比左边大

    那执行刚才的SQL的话,第一条记录是34 ,那我们查找的是22, 是不是就只要到它的左边查找即可,因为右边的数据都比34大,肯定没有22 ,找到22 以后, 搞定 ,I/O次数是不是比刚才的全表扫描的次数少很多,那效率自然就高了。


    索引的数据结构选型

    二叉树 ?

    可以用二叉树吗? 我们知道MySQL一般都有自增主键 ,id之类的字段

    我们来演示下使用二叉树来存储这种自增的数据的话,会怎样?

    https://www.cs.usfca.edu/~galles/visualization/BST.html

    在这里插入图片描述

    那查询

    select * from t where id = 7
    

    在这里插入图片描述

    自增主键的时候 这个二叉树已经退化成链表了。。。。。

    想想,一个几百万数据量的表 ,查找某个大一点的id , 逐个查找比对 (这些数据也是存储在磁盘上的,还得从磁盘上捞啊) 这I/O 这效率可想而知吧…

    二叉树 pass ,不考虑了

    既然退化成链表了,那试试带有平衡功能的树 二叉平衡树 (红黑树)?

    自增主键, 退化为为链表


    红黑树 ?

    二叉树既然在某些情况下会退化成链表, 那如果这棵树能自动平衡呢?

    在这里插入图片描述

    这样子是不可能变成链表了,

    同样 查询

    select * from t where id = 7
    

    在这里插入图片描述

    三次磁盘I/O即可找到, 比刚才二叉树的七次是少了些哈 ,自然查找效率也比二叉树高了

    可如果数据量几百万 上千万呢?

    这棵树 得多高哇。。。

    数据量大, 树高问题

    那既然树高不好, 是不是如果可以控制树的高度(比如 3 到4层的高度,这样查询起来还能接受),让每一层能存储更多的数据,然后再分裂,这样的话数据量相乘起来,也是不少了对吧,这样就能存储更多的数据,这样会不会好一点? ----> B-Tree


    B-Tree ?

    • 叶节点具有相同的深度, 叶节点之间指针为空
    • 所有索引元素不重复
    • 节点中的数据索引从左到右递增排列

    在这里插入图片描述

    叶子节点之间的没有指针,区别于B+树。

    data存储的是数据对应的磁盘地址, k-v结构。

    我们来看下B-Tree的插入 (Max.Degree 设置为3 即 元素到了3个就分裂 )
    在这里插入图片描述

    查找一下

    在这里插入图片描述

    3次

    MySQL也没有使用B-Tree , 因为
    在这里插入图片描述

    除了存储索引以外,还存储了data(数据对应的磁盘地址) , 为了更多的存储数据,MySQL对B-Tree进行了很多改造

    由此演进出了 B+Tree ,将data部分仅保留在叶子节点上,这样的话同等的页可以存储更多而索引数据。


    B+Tree

    • 非叶子节点不存储data,只存储索引(冗余),可以放更多的索引
    • 叶子节点包含所有索引字段
    • 叶子节点用指针连接,提高区间访问的性能

    在这里插入图片描述

    数据仅存储在叶子节点, data可能是磁盘地址也可能是其他的列数据,这个和存储引擎有关系。

    叶子节点之间有指针相连。

    我们来算下 3层高的B+Tree能存储多少数据结构

    假设是BigInt类型的数据

    在这里插入图片描述

    BigInt 占 8个字节 ,同时还是用6个字节存储了它指向的数据的物理地址

    MySQL在使用innodb引擎的时候页大小默认是16K ,查询如下

    mysql> SHOW GLOBAL STATUS like 'Innodb_page_size';
    +------------------+-------+
    | Variable_name    | Value |
    +------------------+-------+
    | Innodb_page_size | 16384 |
    +------------------+-------+
    1 row in set (0.00 sec)
    
    mysql>
    

    假设 树高为3 , 这样的话,第一层即可以存储 16KB * 1024 / (8B + 6B) = 1170

    同样的第二层也是1170 (第二层不是叶子结点,不存储数据)

    第三层,存储数据,一般情况下一行数据的大小肯定不会超过1KB,那我们就按照1KB算吧

    3层高的B+Tree , 存储BitInt可以存储 1170 * 1170 * 16 = 2千1 百万。。。。这效率还是可以的哈

    想一想 如果是4层高的数 1170 * 1170 * 1170 * 16 = 250多亿数据。.。。。

    当然了 都是估算, 如果换成其他类型的数据,每个表的行数据的大小都是相关的,这也就是我们通常说的 MySQL的表到千万级别就要分库分表的理论依据了。

    我们看下B+Tree的插入和查找

    在这里插入图片描述

    在这里插入图片描述


    Hash表

    • 对索引的key进行一次hash计算就可以定位出数据存储的位置
    • 很多时候Hash索引要比B+ 树索引更高效
    • 仅能满足 “=”,“IN”,不支持范围查询
    • hash冲突问题

    在这里插入图片描述

    对索引字段进行hash以后, 还存储了数据对引得磁盘地址。

    一般请款下,hash 比 b+tree的效率要高 ,但工作中绝大部分还是使用的B+Tree , 因为hash对范围查找不是很友好,还要全表扫描

    为啥B+Tree 支持范围查找?

    我们知道B+Tree的叶子节点 有指针相连,从根节点找到对应的叶子节点后, 加上节点本身就是排好序的,所以范围查找就恨轻松了。

    B-Tree 没有指针相连,所以要想范围查找,还得从根节点重新找,效率肯定比B+树低 。


    搞定MySQL

    在这里插入图片描述

    展开全文
  • Mysql索引底层数据结构(B树) 一.什么是B树 B - Trees是一种平衡的多叉树,称为B树(或B-树、B_树),也是数据结构中树形结构的一种。 二.什么是索引,为什么要用要索引 索引是帮助Mysql高效获取数据的排好序的数据...

    Mysql索引底层数据结构(B树)

    一.什么是B树

            B - Trees是一种平衡的多叉树,称为B树(或B-树、B_树),也是数据结构中树形结构的一种。

    二.什么是索引,为什么要用要索引

            索引是帮助Mysql高效获取数据的排好序数据结构,用于快速找出在某个列中有一特定值的行。

            假如数据库有一张表(user)他的字段有col1和col2,我们的表是在我们的磁盘上,如果语句写成select * from user where col1 = 6; 他就会从第一行开始,把磁盘上每一行数据都读取出来,直到查找到col1 = 6的数据,我们如果不进行任何辅助手段帮助查询的话,那么我们查找到这一行数据要进行6次的磁盘I/O。如果我们表的数据是百万级别的,而且数据恰好位于表的底层呢?那要经过多少次的磁盘I/O,效率自然会非常低。 如果没有加索引,查询的数据时就很可能会进行全表扫描。

    三.Mysql中索引用到的数据结构

            上节说到,索引是排好序的数据结构,那么它用到了哪种数据结构?
            如果学过数据结构的朋友估计对二叉树肯定不陌生,二叉树虽然能够解决查询的次数问题,但二叉树一个节点的容量只能存一个索引,查找一个位与整个树底端的数据所用到的次数就会随着整个树的高度增加。那我们如果不想让整个树的高度变得不可控,就可以在横向扩容,设置一个节点的容量,让其能够存储多个索引,那么就引出了B树。
    B - Trees:

    • 一个节点上存储了多个索引元素
    • 节点中数据索引从左到右递增排列
    • 叶节点的指针为空

    B - Trees

    四.Mysql并不是完全使用了B树

    Mysql其实对B树做了些改造,真正的Mysql底层实际上所用到的是B+树(B + Trees)
    B + Trees(B - Trees变种):

    • 非叶子节点不存储data,只存储索引
    • 叶子节点不存储指针
    • 顺序访问指针,提高区间访问性能

    在这里插入图片描述

    五.B + Trees插入过程

            第三节说到B树是对二叉树做了横向上的扩容,会设置一个容量,那么如果要将数据1,2,3,4,5,6,7依次放入最大容量为3的B+树中,它会怎样进行插入。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
            经过上图可以看出B+树的插入是才横向上做文章,一个节点最大容量为3(不能大于等于3),当一个节点的数据容量为3时,它会进行分裂,让其不能大于等于3。
    每个节点递增叶子节点依次递增

            他也符合二叉树的特性,相邻的两个树叉,右边的子元素总是大于等于它的父元素,左边的子元素总是小于它的父元素。
    在这里插入图片描述

    六.使用B+树对数据查询

            不知道大家有没有注意到上图中叶子节点包含我们的所有数据,其实叶子节点是有一种完整的索引元素。非叶子节点把一些中间的元素提取出来做冗余,放到非叶子节点。

            类似一些折半查找,都会把处于中间的元素提取出来做冗余,查找就会更快。

    一般Mysql会把根节点的所有元素放在内存,不需要从磁盘上查找

    比如:要查找的数据为30,30从内存中定位(大于15,小于56),指针经过一次磁盘I/O定位到下一个节点,30继续定位(大于20,小于49),指针进行第二次磁盘I/O定位到30所在节点,总共只进行了两次磁盘I/O,那么它的读取速率是非常快的。
    在这里插入图片描述

    最后给大家推荐一个学习数据结构的网址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

    展开全文
  • MySQL底层索引数据结构

    千次阅读 2017-08-30 17:16:54
    为什么MySQL索引数据结构要选用B Tree 、 B+Tree来实现? 我们来对比一下其他的数据结构: 常见的几种类型:  hash 二叉树  红黑树   索引效率的评价标准是IO次数 局部性原理: 空间上...
  • 深入理解MySQL索引底层数据结构与算法

    万次阅读 多人点赞 2018-10-10 11:10:58
    目录 一 理解索引的特性 二 索引的各种存储结构及其优缺点 ...索引是帮助MySQL高效获取数据的排好序的数据结构 索引存储在文件里 二 索引的各种存储结构及其优缺点 在开始讲这一小节之前,我们先来看一...
  • Mysql索引底层数据结构与算法

    千次阅读 2018-10-10 17:25:44
    2,索引底层数据结构与算法 3,索引最左前缀原理   索引到底是什么 •索引是帮助MySQL高效获取数据的排好序的数据结构 索引的本质 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构...
  • mysql知识点整理】 --- mysql索引底层数据结构

    千次阅读 多人点赞 2020-02-28 12:34:47
    文章目录1 什么是索引 1 什么是索引 索引是帮助MySQL高效的获取数据的数据结构
  • 深入理解Mysql索引底层数据结构与算法

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

    千次阅读 2020-06-09 00:55:00
    了解MySQL索引结构的基本都知道索引BTree类型是用B+树的数据结构,单列索引的结构我们很容易理解,二级索引的每个叶子节点只存储主键关键字外的一个数据,查询起来也很容易在非叶子节点进行大小值判断,最终找到叶子...
  • 这就要从索引的本质以及他的底层原理说起。 索引是什么 那索引到底是什么呢?你是不是还停留在大学学『数据库原理』时老师讲的“索引就像字典的目录”这样的概念?老师讲的没错,但没有深入去讲。 其实...
  • 深入理解 MySQL 索引底层数据结构

    千次阅读 热门讨论 2021-02-27 23:04:08
    ### 数据结构与算法 #### 二分查找法 #### 二叉查找树 #### 平衡二叉树 #### B+树 ### MySQL索引 #### 索引基础 #### 索引类型 ##### B-Tree索引 ##### 哈希索引 ##### 全文索引 #### 索引的优点 #### 高性能的索引 ...
  • 主讲存储结构:https://blog.csdn.net/qq_41618510/article/details/84702890 主讲数据存储:https://blog.csdn.net/qq_41618510/article/details/84702890 主讲存储引擎:https://blog.csdn.net/qq_416...
  • MySQL索引底层数据结构

    千次阅读 2018-12-02 12:06:34
    首先,在讨论数据结构之前,先了解一下MySQL的存储引擎和数据存取原理。 这里有一篇关于存储引擎的文章:https://blog.csdn.net/qq_41618510/article/details/84680226 下图是分别用InnoDB和Myisam引擎存储数据的...
  • 索引 使用索引,会提前存储被索引字段对应行的磁盘文件地址指针,做一...数据结构可视化网站 红黑树 单边增长不平衡时,红黑树会自动平衡。 JDK1.8之后,HashMap使用的就是红黑树。 在某些场景下,红黑树也会存在问...
  • MYSQL索引底层数据结构

    千次阅读 2018-07-07 16:34:24
    特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等。为了避免混乱,本文将只关注于BTre...
  • 索引是一种排好序的数据结构mysql目前默认使用的是b+树。 2.为什么使用b+树? 例如表table 数据 id name 1 zs 2 ls 3 sa 4 zl 5 wmz 6 zs 7 sd 这这个表里,...
  • mysql存储引擎MyISAM与InnoDB的底层数据结构的区别主要有,在磁盘上存储的文件以及存储索引以及组织存储索引的方式不同; MyISAM索引文件和数据文件是分离的(非聚集),索引的叶节点存放的是对应索引在文件系统中的...
  • 数据库(DataBase)是存放用户数据的地方,当用户访问、操作数据库中的数据时,需要数据库管理系统的帮助。数据管理系统的全称是DataBase Management System,... MySQL是一种关系数据库管理系统,关系数据库将数据...
  • mysql中,索引就是帮助mysql快速找到某条数据的一种数据结构,它是排好序的,独立于mysql表数据之外的。 索引数据结构分为哪几种 二叉树、红黑树、Hash表、B树。 在这里我们主要介绍hash表和B树 Hash表 什么是hash...
  • MySQL索引的本质,MySQL索引的实现,MySQL索引的数据结构
  • 1. MyIsam是非聚集索引(其实MyIsam引擎就是索引和数据分离的索引单独放在一个XX.MYI文件中,数据单独放在一个XX.MYD文件中),InnoDB就是聚集索引(其实就是他的数据和索引就是在一个XX.IDB文件中),或者说MyIsam...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 99,575
精华内容 39,830
关键字:

mysql底层数据结构

mysql 订阅
数据结构 订阅