精华内容
下载资源
问答
  • 联合索引的分支块包含索引键值列以及相应的指针,但不是叶子块的所有键值都列举在分支块里,具体跟分支块的指针有关系:不管是联合索引还是单列索引,分支块都包含两种指针,一种叫LMC,另一种就是分支块的索引行...

    联合索引的分支块包含索引键值列以及相应的指针,但不是叶子块的所有键值都列举在分支块里,具体跟分支块的指针有关系:

    不管是联合索引还是单列索引,分支块都包含两种指针,一种叫LMC,另一种就是分支块的索引行对应的指针。

    1.LMC,left most child,每个分支块都会有一个,而且只会有一个,这个指针指向一个索引叶子块,这个LMC指针的特征是,所指向的叶子块,其所包含的索引键值的最大值,小于该分支块所有索引键值的最小值。例如分支的索引键值为(AD,AK,...),那么LMC所指向的叶子块的索引列值只能是排在AD前面的键值,例如AB,AC等;

    2.分支块的索引行对应的指针,首先明确,一个分支块指向多个叶子块,但并不是叶子块里的所有键值都列举在叶子块里。叶子块的内容除了上述说的LMC,其余的即是索引键值+对应的指针,而这个指针所指向的叶子块,其所包含的最小键值都要比该指针在分支块里对应的索引键值大。例如分支块的索引行是AD+指针,那么这个指针所指向的叶子块的最小键值必须比AD大,可以是ADF,可以是AK,但不能是AC。也就是说,分支块的每一个索引行对应的指针,都指向一个叶子块,且指向的叶子块的索引键的最小值,都比这个索引键值大。

    图就不画了,脑补吧~

    展开全文
  • 前言最近在学习MySQL的...但许多文章讲述的都是单列索引,我很好奇联合索引对应的结构图是怎样的。疑惑:联合索引的结构是怎样的比方说联合索引 (col1, col2,col3),我知道在逻辑上是先按照col1进行排序再按照col2进...

    前言

    最近在学习MySQL的存储引擎和索引的知识。看了许多篇介绍MyISAM和InnoDB的索引的例子,都能理解。

    像这张索引图:

    19b414117d7e7c27b4bb3cede121103c.png

    PS:该图来自大神张洋的《MySQL索引背后的数据结构及算法原理》一文。

    但许多文章讲述的都是单列索引,我很好奇联合索引对应的结构图是怎样的。

    疑惑:联合索引的结构是怎样的

    比方说联合索引 (col1, col2,col3),我知道在逻辑上是先按照col1进行排序再按照col2进行排序最后再按照col3进行排序。因此如果是select * from table where col1 = 1 and col3 = 3的话,只有col1的索引部分能生效。但是其物理结构上这个联合索引是怎样存在的,我想不懂。

    解答:联合索引的结构

    上网查阅了许多资料,总算有点眉目了。

    假设这是一个多列索引(col1, col2,col3),对于叶子节点,是这样的:

    b9ebdc4d9aa7a27c5146f5cb571e86c0.png

    PS:该图改自《MySQL索引背后的数据结构及算法原理》一文的配图。

    也就是说,联合索引(col1, col2,col3)也是一棵B+Tree,其非叶子节点存储的是第一个关键字的索引,而叶节点存储的则是三个关键字col1、col2、col3三个关键字的数据,且按照col1、col2、col3的顺序进行排序。

    配图可能不太让人满意,因为col1都是不同的,也就是说在col1就已经能确定结果了。自己又画了一个图(有点丑),col1表示的是年龄,col2表示的是姓氏,col3表示的是名字。如下图:

    2e969b02ce15354e2a684e02c97ecc54.png

    PS:对应地址指的是数据记录的地址。

    如图,联合索引(年龄, 姓氏,名字),叶节点上data域存储的是三个关键字的数据。且是按照年龄、姓氏、名字的顺序排列的。

    因此,如果执行的是:

    select * from STUDENT where 姓氏='李' and 名字='安';

    或者

    select * from STUDENT where 名字='安';

    那么当执行查询的时候,是无法使用这个联合索引的。因为联合索引中是先根据年龄进行排序的。如果年龄没有先确定,直接对姓氏和名字进行查询的话,就相当于乱序查询一样,因此索引无法生效。因此查询是全表查询。

    如果执行的是:

    select * from STUDENT where 年龄=1 and 姓氏='李';

    那么当执行查询的时候,索引是能生效的,从图中很直观的看出,age=1的是第一个叶子节点的前6条记录,在age=1的前提下,姓氏=’李’的是前3条。因此最终查询出来的是这三条,从而能获取到对应记录的地址。

    如果执行的是:

    select * from STUDENT where 年龄=1 and 姓氏='黄' and 名字='安';

    那么索引也是生效的。

    而如果执行的是:

    select * from STUDENT where 年龄=1 and 名字='安';

    那么,索引年龄部分能生效,名字部分不能生效。也就是说索引部分生效。

    因此我对联合索引结构的理解就是B+Tree是按照第一个关键字进行索引,然后在叶子节点上按照第一个关键字、第二个关键字、第三个关键字…进行排序。

    最左原则

    而之所以会有最左原则,是因为联合索引的B+Tree是按照第一个关键字进行索引排列的。

    有助于理解联合索引的一个例子

    from csdn论坛:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

    22

    23

    24

    25

    26

    27

    28

    29

    30

    31

    32

    33

    34

    35

    36

    37

    38

    39

    40

    41

    假设数据 表T (a,b,c) rowid 为物理位置

    rowid a b c

    (1)   1 1 1

    (2)   2 1 13

    (3)   2 2 14

    (4)   1 3 3

    (5)   2 3 12

    (6)   1 2 5

    (7)   2 3 9

    (8)   1 2 2

    (9)   1 3 6

    (10)  2 2 11

    (11)  2 2 8

    (12)  1 1 7

    (13)  2 3 15

    (14)  1 1 4

    (15)  2 1 10

    当你创建一个索引create index xxxon t(a,b),

    则索引文件逻辑上等同于如下

    a b rowid

    1 1 1

    1 1 12

    1 1 14

    1 2 6

    1 2 8

    1 3 4

    1 3 9

    2 1 2

    2 1 15

    2 2 3

    2 2 10

    2 2 11

    2 3 5

    2 3 7

    2 3 13

    当select *from Twhere a=1and b=3 的时候,

    数据库系统可以直接从索引文件中直接二分法找到A=1的记录,

    然后再B=3的记录。

    但如果你where b=3 则需要遍历这个索引表的全部!

    最后

    这样的解释,参考过别人的文章,自己也有思考过,但并不能确定实际上的结构就是这种。但是,也算是学到了许多东西,像是明白了为什么会有最左原则的存在。

    原文链接

    展开全文
  • 单列索引其实也可以看做联合索引,索引列为1的联合索引,从下就可以看出联合索引的底层存储跟单列索引时类似的,区别在于联合索引是每个树节点中包含多个索引值,在通过索引查找记录时,会先将联合索引中第一个...

     

     

    单列索引其实也可以看做联合索引,索引列为1的联合索引,从下图就可以看出联合索引的底层存储跟单列索引时类似的,区别在于联合索引是每个树节点中包含多个索引值,在通过索引查找记录时,会先将联合索引中第一个索引列与节点中第一个索引值进行匹配,匹配成功接着匹配第二个索引列和索引值,直到联合索引的所有索引列都匹配完;如果过程中出现某一个索引列与节点相应位置的索引值不匹配的情况,则无需再匹配节点中剩余索引列,前往下一个节点。

     

     

     

    展开全文
  • 联合索引的树结构、最左匹配原则、如何选择合适的索引列顺序、索引下推图文讲解

    联合索引

    联合索引(也叫组合索引、复合索引、多列索引)是指对表上的多个列进行索引。联合索引的创建方法跟单个索引的创建方法一样,不同之处仅在于有多个索引列。

    例如,创建如下表,idx_name 是联合索引,索引列为 (name,age)

    CREATE TABLE `t_user` (
      `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键',
      `name` varchar(32) NOT NULL COMMENT '姓名',
      `age` tinyint(3) unsigned NOT NULL COMMENT '年龄',
      `gender` tinyint(3) unsigned NOT NULL COMMENT '性别:1男,0女',
      PRIMARY KEY (`id`),
      KEY `idx_name` (`name`,`age`)
    ) ENGINE=InnoDB DEFAULT CHARSET=utf8;
    

    假如表中有如下数据

    id name age gender
    1 LiLei 18 1
    2 HanMeimei 17 0
    3 Lucy 17 0
    4 Lili 16 0
    5 WeiHua 32 0
    6 ZhangWei 25 1
    7 Ann 36 0
    8 Lisa 19 0
    9 ZhangWei 18 1
    10 Kate 17 1

    我们来看一下这棵索引树的结构
    在这里插入图片描述

    从图中我们可以看出,叶子节点中的键值都是按顺序存储的,即(“Ann”,36)、(“HanMeimei”,17)、(“Kate”,17)、(“LiLei”,18)、(“Lili”,16)、(“Lisa”,19)、(“Lucy”,17)、(“WeiHua”,32)、(“ZhangWei”,18)、(“ZhangWei”,25)。

    索引会先根据 name 排序,如果 name 相同,再根据 age 进行排序。

    联合索引的最左匹配原则

    索引的目的其实就是为了提高数据查询的效率,联合索引也一样,使用联合索引时,一定要注意符合最左匹配原则:在通过联合索引检索数据时,从索引中最左边的列开始,一直向右匹配,如果遇到范围查询(>、<、between、like等),就停止后边的匹配。

    假如对字段 (a, b, c) 建立联合索引,如下查询语句可以使用到索引:

    where a = xxx
    where a = xxx and b = xxx
    where a = xxx and b = xxx and c = xxx
    where a like 'xxx%'
    where a > xxx
    where a = xxx order by b
    where a = xxx and b = xxx order by c
    group by a
    

    当然,像如下:

    where b = xxx and a = xxx
    where a = xxx and c = xxx and b = xxx
    

    这种查询条件书写顺序不影响对联合索引的使用,因为执行 sql 的时候,MySQL优化器会帮我们调整 where 后 a,b,c 的顺序,让我们用上索引。

    而还有一些语句是只能用到联合索引的一部分的。

    where a = xxx and c = xxx 可以用到 a 列的索引,用不到 c 列索引。

    where a like 'xxx%' and b = xxx 可以用到 a 列的索引,用不到 b 列的索引。

    where a > xxx and b = xxx 可以用到 a 列的索引,用不到 b 列的索引。

    最需要注意类似下边的这些查询

    where b = xxx
    where c = xxx
    where a like '%xxx'			-- 不满足最左前缀
    where d = xxx order by a	-- 出现非排序使用到的索引列 d 
    where a + 1 = xxx	-- 使用函数、运算表达式及类型隐式转换等
    

    这些查询语句,完全用不到 (a, b, c) 这个联合索引。

    如何选择合适的索引列顺序

    建立联合索引时,一般我们遵循的经验是:将选择性最高的列放在索引的最前列。这在某些场景下比较有用,但通常不如避免随机IO和排序那么重要。正确的顺序应该依赖于使用该索引的查询,并且同时需要考虑如何更好的满足排序和分组的需要。

    where a = xxx and b = xxx and c = xxx 如果我们的查询是这样的,建索引时,就可以考虑将选择性高的列放在索引的最前列,选择性低的放后边。

    如果是 where a > xxx and b = xxxwhere a like 'xxx%' and b = xxx 这样的语句,可以对 (b, a) 建立索引。

    如果是 where a = xxx order by b 这样的语句,可以对 (a, b) 建立索引。

    索引下推(索引条件下推)

    什么是索引下推(Index Condition Pushdown,ICP)呢?我们通过例子来了解下。

    假设我们想从一开始创建的表中,查询 name 以 ‘L’ 开头,并且 age 为 17 的人员信息。

    select * from t_user where name like 'L%' and age = 17;
    

    在不用索引下推的情况下,根据前边"最左匹配原则"描述的那样,该查询在联合索引中只有 name 列可以使用到索引,age 列是用不到索引的。在扫描 (‘name’, age) 索引树时,根据 name like 'L%' 这个条件,可以查找到 LiLeiLiliLisaLucy 四条索引数据,接下来,再根据这四条索引数据中的 id 值,逐一进行回表扫描,从聚簇索引中找到相应的行数据,将找到的行数据返回给 server 层。server 层中,再根据 age = 17 这个条件进行筛选,最终只留下 Lucy 用户的数据信息。

    不用索引下推的过程,如下图示:
    在这里插入图片描述

    在使用索引下推的情况下,存储引擎层还是先根据 name like 'L%' 这个条件,查找到 LiLeiLiliLisaLucy 四条索引数据,不过接下来不是直接进行回表操作,而是根据 age = 17 这个条件,对四条索引数据进行判断筛选,将符合条件的索引对应的 id 进行回表扫描,最终将找到的行数据返回给 server 层。(也就是我们把本应该在 server 层进行筛选的条件,下推到存储引擎层来进行筛选判断了。这个下推的前提是索引中有 age 列信息,如果是其它条件,如 gender = 0,这个即使下推下来也没用)

    使用索引下推的过程,如下图示:
    在这里插入图片描述

    由上比较可以看出,使用索引下推优化,可以有效减少回表次数,也可以减少 server 层从存储引擎层接收数据的次数,从而大大提升查询效率。

    索引下推是 MySQL 5.6 及以上版本上推出的,用于对查询进行优化。默认情况下,索引下推处于启用状态。我们可以使用如下命令来开启或关闭。

    set optimizer_switch='index_condition_pushdown=off'; 	-- 关闭索引下推
    set optimizer_switch='index_condition_pushdown=on';		-- 开启索引下推
    

    话说,正常情况下,我们有什么理由来关闭这么好用的功能呢?

    展开全文
  • 联合索引在B+树上的存储结构 联合索引的查找方式 为什么会有最左前缀匹配原则 在分享这篇文章之前,我在网上查了关于MySQL联合索引在B+树上的存储结构这个问题,翻阅了很多博客和技术文章,其中有几篇讲述的与事实...
  • 在什么是索引这篇文章中介绍了索引的常见的数据结构,其对应数据结构是以主键索引来讲解的。本文我们一起看下联合使用在B+树的结构是怎么样的? 联合索引是什么 对多个字段同时建立的索引(有顺序,ABC,CBA是...
  • 前言 最近在学习MySQL的存储引擎和索引的知识...但许多文章讲述的都是单列索引,我很好奇联合索引对应的结构图是怎样的。 疑惑:联合索引的结构是怎样的 比方说联合索引 (col1, col2,col3),我知道在逻辑上是先按...
  • 联合索引在B+树上的结构介绍

    万次阅读 多人点赞 2018-11-14 10:28:07
    前言 最近在学习MySQL的存储引擎和索引的...但许多文章讲述的都是单列索引,我很好奇联合索引对应的结构图是怎样的。 疑惑:联合索引的结构是怎样的 比方说联合索引 (col1, col2,col3),我知道在逻辑上是先按照co...
  • 前言 最近在学习MySQL的存储引擎和索引的...但许多文章讲述的都是单列索引,我很好奇联合索引对应的结构图是怎样的。 疑惑:联合索引的结构是怎样的 比方说联合索引 (col1, col2,col3),我知道在逻辑上是先按照col1...
  • 联合索引

    2017-07-27 13:27:36
    我们知道,对于表的单列(如id)数据,是可以建立索引的,对于多列(id和name组合,... 联合索引也满足这三个特征,但这里的逻辑就不画了,而是以更直观的方式来展现其查找逻辑,这里应注意,联合索引的列有前后,以i
  • 今天了解到联合索引的数据结构,引发了一些思考,特此记录一下。 记录几张数据结构的图片: 原文在:https://blog.csdn.net/ibigboy/article/details/104571930?depth_1-
  • mysql聚集索引,非聚集索引,联合索引 mysql索引是一个排好序的数据结构,mysql底层选用的是B+树结构,会自动将索引从左往右从小到大依次排好序,如下: 看叶子节点,可以发现是从左到右从小到大排好序的结构。...
  • 联合索引失效原理

    2020-10-20 13:12:08
    开局一张,由数据库的a字段和b字段组成一个联合索引。 从本质上来说,联合索引也是一个B+树,和单值索引不同的是,联合索引的键值对不是1,而是大于1个。 a, b 排序分析 a顺序:1,1,2,2,3,3 b顺序:1,2,1...
  • mysql联合索引

    2018-02-13 15:29:00
    假定数据表有一个包含2列的联合索引(a, b),则索引的B+树结构可能如下: 从中可以看出:B+树先按a排序,然后按b排序,所以从全局看,a是全局有序的,而b则不是。 建表: create table t_u_...
  • 是什么:索引是一组按照特定规则排好序的数据所组成的数据结构 为什么:快速定位数据 B+树 特点 每个节点可以有多个索引数据 自平衡 叶子节点组成链表 非叶子节点只存放索引值 如...... 聚集(聚簇)索引 基本...
  • 这里写目录标题1 二叉树2 红黑树(jdk8 HashMap)2.1 红黑树增加数据2.2 删除数据3 HASH4 BTREE5 B+Tree(MYSQL)6 MyISAM索引实现(非聚集,...引擎是表级别的不是数据库级别的)7 InnoDB索引实现(聚集)8 联合索引...
  • 它的索引结构是一个键值对应很多行(rowid),对于报表类数据库,重复率高的数据,特定类型的查询例如count、or、and等逻辑操作,只需要进行位运算即可得到我们需要的结果,可以说是相当的效率。最近项目在进行上云...
  • 点击上方“Java面试题精选”,关注公众号...索引是对数据库表中的一列或多列值进行排序的一种结构,使用索引可以快速访问数据库表中的特定信息。二、索引的作用?索引相当于图书上的目录,可以根据目录上的页码快...
  • 索引是为了加速数据的检索,但是不合理的表结构或适应不当则会起到反作用。我们在项目中就遇到过类似的问题,两个十万级别的数据表,在做连接查询的时候,查询时间达到了7000多秒还没有查出结果。 首先说明,关联的...
  • Mysql的B+树索引在单列索引上比较好理解,结构如下:那组合索引的B+树存储结构是什么样的呢,为什么会有最左前缀原理,看了很多帖子找到了答案数据表B+树结构b c d设置组合索引对于联合索引来说只不过比单值索引多了...
  • 文章目录磁盘存取原理数据结构二叉树:红黑树:B-TREE:B+TREEB-TREE数据存储方式:mysql的B+TREE数据存储方式mysql存储引擎MyISAMInnoDB联合索引的底层数据结构字符串类型多种数据类型组成的联合索引 磁盘存取原理...
  • 这里写目录标题索引数据结构二叉搜索树红黑树Hash表B-TreeB+Tree索引是怎么支撑千万级表的快速查找存储引擎MyISAM(非聚集)InnoDB(聚集)联合索引底层数据结构 索引数据结构 二叉搜索树 对于二叉搜索树来说,他的...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 121
精华内容 48
关键字:

联合索引结构图