写点什么

Java 岗大厂面试百日冲刺 - 日积月累,每日三题【Day28】—

作者:Java高工P7
  • 2021 年 11 月 11 日
  • 本文字数:4027 字

    阅读完需:约 13 分钟

聚集索引 和 非聚集索引的区别:


  1. 单表中只能有一个聚集索引,而非聚集索引单表可以存在多个。

  2. 聚集索引,索引中键值的逻辑顺序决定了表中相应行的物理顺序;非聚集索引,索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同

  3. 索引是通过二叉树的数据结构来描述的,我们可以这么理解聚簇索引:索引的叶节点就是数据节点。而非聚簇索引的叶节点仍然是索引节点,只不过有一个指针指向对应的数据块

  4. 聚集索引:物理存储按照索引排序;非聚集索引:物理存储不按照索引排序;


追问 1:为什么聚集索引可以创建在任何一列上,如果此表没有主键约束,即有可能存在重复行数据呢?




乍一看,这还真是和聚集索引的约束相背,但实际情况真可以创建聚集索引。


其原因是:如果未使用 UNIQUE 属性创建聚集索引,数据库引擎将向表自动添加一个四字节 uniqueifier列。必要时,数据库引擎 将向行自动添加一个 uniqueifier 值,使每个键唯一。此列和列值供内部使用,用户不能查看或访问。


追问 2:聚集索引一定比非聚集索引性能优么?




如果想查询学分在 60-90 之间的学生的学分以及姓名,在学分上创建聚集索引是否是最优的呢?


并不是。既然只输出两列,我们可以在学分以及学生姓名上创建联合非聚集索引,此时的索引就形成了覆盖索引,即索引所存储的内容就是最终输出的数据,这种索引当然比以学分为聚集索引做查询性能好,算是相当于联合聚集索引~~灵活运用即可。





陈小哈,一个爱睡懒觉的崽子。工作日的它却总爱发呆~




面试题 2:说一说你对 B 树 和 B+树 的理解吧


=======================================================================================


1、B树(Balanced Tree)多路平衡查找树 多叉


B 树是一种多路自平衡搜索树,它类似普通的二叉树,但是 B 书允许每个节点有更多的子节点。B 树示意图如下:值得注意的是,B树的非叶子节点和叶子结点的data数据都是分开存储的,那么针对范围查询、排序等常用特性就很不友好了。


![在这里插入图片描述](https://img-blog.csdnimg.cn/20200825092939538.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5


【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


MzkwNTQ1,size_16,color_FFFFFF,t_70#pic_center)


B 树的特点:


  1. 所有键值分布在整个树中

  2. 任何关键字出现且只出现在一个节点中

  3. 搜索有可能在非叶子节点结束

  4. 在关键字全集内做一次查找,性能逼近二分查找算法


为了提升效率,要尽量减少磁盘 I/O 的次数。实际过程中,磁盘并不是每次严格按需读取,而是每次都会预读。


磁盘读取完需要的数据后,会按顺序再多读一部分数据到内存中,这样做的理论依据是计算机科学中注明的局部性原理:


  • 由于磁盘顺序读取的效率很高(不需要寻址时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高 I/O 效率.预读的长度一般为页(page)的整倍数。

  • MySQL(默认使用 InnoDB 引擎),将记录按照页的方式进行管理,每页大小默认为 16K(可以修改)。


B-Tree 借助计算机磁盘预读机制:


每次新建节点的时候,都是申请一个页的空间,所以每查找一个节点只需要一次 I/O;因为实际应用当中,节点深度会很少,所以查找效率很高.


2、B+ Tree (B+树是 B 树的变体,也是一种多路搜索树)



从图中也可以看到,B+树与 B 树的不同在于:


  1. 所有关键字存储在叶子节点,非叶子节点不存储真正的 data,从而可以快速定位到叶子结点。

  2. 为所有叶子节点增加了一个链指针意味着所有的值都是按顺序存储的,并且每一个叶子页到根的距离相同,很适合查找范围数据。说明支持范围查询和天然排序。


因此,B+Tree 可以对<,<=,=,>,>=,BETWEEN,IN,以及不以通配符开始的 LIKE 使用索引。且如果用到了该索引,排序功能的消耗大大减少。


B+树的优点:


比较的次数均衡,减少了 I/O 次数,提高了查找速度,查找也更稳定。


  • B+树的磁盘读写代价更低

  • B+树的查询效率更加稳定


要知道的是,你每次创建表,系统会为你自动创建一个基于 ID 的聚集索引(上述 B+树),存储全部数据;你每次增加索引,数据库就会为你创建一个附加索引(上述 B+树),索引选取的字段个数就是每个节点存储数据索引的个数,注意该索引并不存储全部数据。





课间休息,又来秀一下来自咱们群里同学的搬砖工地,坐标:深圳


作者:晓海wiley




面试题 3:说一下你对最左前缀原则的理解吧


===================================================================================


通常我们在建立联合索引的时候,相信建立过索引的同学们会发现,无论是 Oracle 还是 MySQL 都会让我们选择索引的顺序,比如我们想在 a,b,c 三个字段上建立一个联合索引,我们可以选择自己想要的优先级,(a、b、c),或是 (b、a、c) 或者是(c、a、b) 等顺序。



为什么数据库会让我们选择字段的顺序呢?不都是三个字段的联合索引么?这里就引出了数据库索引的最重要的原则之一,最左匹配原则


在我们开发中经常会遇到这种问题,明明这个字段建了联合索引,但是 SQL 查询该字段时却不会使用这个索引。难道这索引是假的?白嫖老子资源?!



比如索引 abc_index:(a,b,c)是 a,b,c 三个字段的联合索引,下列 sql 执行时都无法命中索引 abc_index;


select * from table where c = '1';


select * from table where b ='1' and c ='2';


以下三种情况却会走索引:


select * from table where a = '1';


select * from table where a = '1' and b = '2';


select * from table where a = '1' and b = '2' and c='3';


从上面两个例子大家有木有看出点眉目呢?


是的,索引 abc_index:(a,b,c),只会在 where 条件中带有(a)、(a,b)、(a,b,c)的三种类型的查询中使用。其实这里说的有一点歧义,其实当 where 条件只有(a,c)时也会走,但是只走 a 字段索引,不会走 c 字段。


那么这都是为什么呢?我们一起来看看其原理吧。


一、最左匹配原则的原理


MySQL 建立多列索引(联合索引)有最左匹配的原则,即最左优先:


如果有一个 2 列的索引 (a, b),则已经对 (a)、(a, b) 上建立了索引;


如果有一个 3 列索引 (a, b, c),则已经对 (a)、(a, b)、(a, b, c) 上建立了索引;


假设数据 表 LOL (id,sex,price,name) 的物理位置(表中的无序数据)如下:


(注:下面数据是测试少量数据选用的,只为了方便大家看清楚。实际操作中,应按照使用频率、数据区分度来综合设定索引顺序~)


主键 id sex(a) price(b) name(c)


(1) 1 1350 AAA 安妮


(2) 2 6300 MMM 盲僧


(3) 1 3150 NNN 奈德丽


(4) 2 6300 CCC 锤石


(5) 1 6300 LLL 龙女


(6) 2 3150 EEE 伊泽瑞尔


(7) 2 6300 III 艾克


(8) 1 6300 BBB 暴走萝莉


(9) 1 4800 FFF 发条魔灵


(10) 2 3150 KKK 卡牌大师


(11) 1 450 HHH 寒冰射手


(12) 2 450 GGG 盖伦


(13) 2 3150 OOO 小提莫


(14) 2 3150 DDD 刀锋之影


(15) 2 6300 JJJ 疾风剑豪


(16) 2 450 JJJ 剑圣


当你在 LOL 表创建一个联合索引 abc_index:(sex,price,name)时,生成的索引文件逻辑上等同于下表内容(分级排序)


sex(a) price(b) name(c) 主键 id


1 450 HHH 寒冰射手 (11)


1 1350 AAA 安妮 (1)


1 3150 NNN 奈德丽 (3)


1 4800 FFF 发条魔灵 (9)


1 6300 BBB 暴走萝莉 (8)


1 6300 LLL 龙女 (5)


2 450 GGG 盖伦 (12)


2 450 JJJ 剑圣 (16)


2 3150 DDD 刀锋之影 (14)


2 3150 EEE 伊泽瑞尔 (6)


2 3150 KKK 卡牌大师 (10)


2 3150 OOO 小提莫 (13)


2 6300 CCC 锤石 (4)


2 6300 III 艾克 (7)


2 6300 JJJ 疾风剑豪 (15)


2 6300 MMM 盲僧 (2)


小伙伴儿们有没有发现 B+树联合索引的规律?感觉还有点模糊的话,那咱们再来看一张索引存储数据的结构图,或许更明了一些。



这是一张来自思否上的图片,层次感很清晰,小伙伴可以看到,对于 B+树中的联合索引,每级索引都是排好序的。联合索引 bcd_index:(b,c,d) , 在索引树中的样子如图 , 在比较的过程中 ,先判断 b 再判断 c 然后是 d 。


由上图可以看出,B+ 树的数据项是复合的数据结构,同样,对于我们这张表的联合索引 (sex,price,name)来说 ,B+ 树也是按照从左到右的顺序来建立搜索树的,当 SQL 如下时:


select sex,price,name from LOL where sex = 2 and price = 6300 and name = 'JJJ 疾风剑豪';


B+ 树会优先比较 sex 来确定下一步的指针所搜方向,如果 sex 相同再依次比较 price 和 name,最后得到检索的数据;


二、违背最左原则导致索引失效的情况


(下面以联合索引 abc_index:(a,b,c) 来进行讲解,便于理解)


1、查询条件中,缺失优先级最高的索引 “a”


where b = 6300 and c = 'JJJ疾风剑豪' 这种没有以 a 为条件来检索时;B+树就不知道第一步该查哪个节点,从而需要去全表扫描了(即不走索引)。因为建立搜索树的时候 a 就是第一个比较因子,必须要先根据 a 来搜索,进而才能往后继续查询 b 和 c,这点我们通过上面的存储结构图可以看明白。


2、查询条件中,缺失优先级居中的索引 “b”


当 where a =1 and c =“JJJ 疾风剑豪” 这样的数据来检索时;B+ 树可以用 a 来指定第一步搜索方向,但由于下一个字段 b 的缺失,所以只能把 a = 1 的数据主键 ID 都找到,通过查到的主键 ID 回表查询相关行,再去匹配 c = ‘JJJ 疾风剑豪’ 的数据了,当然,这至少把 a = 1 的数据筛选出来了,总比直接全表扫描好多了。

用户头像

Java高工P7

关注

还未添加个人签名 2021.11.08 加入

还未添加个人简介

评论

发布
暂无评论
Java岗大厂面试百日冲刺 - 日积月累,每日三题【Day28】—