文档章节

【BATJ】面试必问MySQL索引实现原理

须臾之余
 须臾之余
发布于 05/22 21:24
字数 1940
阅读 48
收藏 10

BATJ面试题剖析

1、为什么需要使用索引?

2、数据结构Hash、平衡二叉树、B树、B+区别?

3、机械硬盘、固态硬盘区别?

4、Myisam与Innodb B+树的区别?

5、MySQL中的索引什么数据结构?

6、MySQL数据库优化方案?

1.为什么需要使用索引?

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

也就是说:索引就像书的目录一样可以非常快速的定位到书的页码。

如果向mysql发出一条sql语句请求,查询的字段没有创建索引的话,可能会导致全表扫描,这样查询效率非常低

2.1数据结构Hash算法

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表

优点:通过字段的值计算的hash值,定位数据非常快,查找可以直接根据key访问。

缺点: 因为底层数据结构是散列的,无法进行比较大小,不能进行范围查找

index=Hash(key)

2.2数据结构平衡二叉树算法

平衡二叉查找树,又称 AVL树。 它除了具备二叉查找树的基本特征之外,还具有一个非常重要的特点:它 的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1。 也就是说AVL树每个节点的平衡因子只可能是-1、0和1(左子树高度减去右子树高度)。

数据结构模拟工具

官网首页:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Avl数据结构https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

平衡二叉树 查询原理

假设查询10 (需要经历4次IO操作)

1次 从硬盘中读取4 (内存),判断下10>4,取右指针
2次 从硬盘中读取8 (内存),判断下10>8,取右指针
3次 从硬盘中读取9 (内存),判断下10>,取右指针
4次 从硬盘中读取10 (内存),判断下10=10,定位到数据

优点:平衡二叉树算法基本与二叉树查询相同,效率比较高

缺点:插入操作需要旋转,支持范围查询,虽然支持范围查询,但是回旋查询效率低

规律:如果树的高度越高,那么查询IO次数会越多。

2.3数据结构B

维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库文件系统

因为B树节点元素比平衡二叉树要多,所以B树数据结构相比平衡二叉树数据结构实现减少磁盘IO的操作

如何去减少查询IO次数?

B树在平衡二叉树中,减少树的高度

结论:B树比平衡二叉树减少了一次IO操作

B树查询效率比平衡二叉树效率要高,因为B树的节点中可以有多个元素,从而减少树的高度,减少IO操作,从而提高查询效率,缺点:范围查询效率还是比较低。

2.4数据结构B+

B+树相比B树,新增叶子节点与非叶子节点关系,叶子节点中包含了keyvalue,非叶子节点中只是包含了key,不包含value。

所有相邻的叶子节点包含非叶子节点,使用链表进行结合,有一定顺序排序,从而范围查询效率非常高

B+树 解决范围查询问题、减少IO查询的操作。

B+树算法: 通过继承了B树的特征,通过非叶子节点查询叶子节点获取对应的value,所有相邻的叶子节点包含非叶子节点,使用链表进行结合,有一定顺序排序,从而范围查询效率非常高

缺点:因为有冗余节点数据,会比较占内存

3、机械硬盘、固态硬盘区别?

固态硬盘对比机械硬盘优势图表

4、Myisam与Innodb B+树的区别?

索引文件如何查看

默认数据与索引文件位置: /var/lib/mysql

MyISAM引擎的文件:

.myd my data,表数据文件

.myi my index,索引文件

.log 日志文件

InnoDB引擎的文件

采用表空间(tablespace)来管理数据,存储表数据和索引,

InnoDB数据库文件(即InnoDB文件集,ib-file set):

ibdata1ibdata2等:系统表空间文件,存储InnoDB系统信息和用户数据库表数据和索引,所有表共用。

.ibd文件:单表表空间文件,每个表使用一个表空间文件(file per table),存放用户数据库表数据和索引。

MyISAMInnoDBB-Tree索引不同的实现方式

主键索引: MyISAM引擎使用B+Tree作为索引结构叶节点的data域存放的是数据记录的地址。下图是MyISAM主键索引的,这里设表一共有三列,假设我们以Col1为主键,图myisam1是一个MyISAM表的主索引(Primary key)示意。可以看出

InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同.

 MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

5、MySQL中的索引什么数据结构?

使用B+Tree作为索引结构,使用InnoDB引擎,叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

6、MySQL数据库优化方案?

Mysql的优化,大体可以分为三部分:索引的优化,sql慢查询优化,表的优化

开启慢查询日志,可以让MySQL记录下查询超过指定时间的语句,通过定位分析性能的瓶颈,才能更好的优化数据库系统的性能。

                              先捕获低效SQL→慢查询优化方案→慢查询优化原则

讯云MySQL数据库监控

版权@须臾之余https://my.oschina.net/u/3995125

1.腾讯云数据库地址:https://console.cloud.tencent.com/cdb

2. 实例监控https://console.cloud.tencent.com/cdb?ins=4-cdb-0g6a8qct

© 著作权归作者所有

须臾之余
粉丝 65
博文 33
码字总数 55128
作品 0
吉安
程序员
私信 提问
头条 offer,记一次 JAVA 面试经历和总结

作者:“想去大厂的小菜鸡” 投稿 国庆期间公司的项目很闲,很多人觉得没意思陆续走了,我也考虑到自己的发展,从9月底开始面,面到11月底,三十家公司。我从不打没准备的仗,我是一个喜欢总...

Tamic
2018/12/15
0
0
6个offer,10家公司,25场面试,从美团到头条,我的求职之路!

简介:文章的笔者是三四月时跳槽换工作,对面试经验做一些总结,今后也是总结自己工作中遇到的一些问题分享给大家,算是一个开始吧! 跳槽经历分为定位、准备、简历、面试这四个部分,本篇文...

java知识分子
05/24
0
0
经过了这么多场Java面试,我明白了这些道理

最近3个月一口气面了十几家公司的Java开发岗,大大小小的面试笔试加起来快20场,收获很多。本人毕业快2年了,毕业时在学校所在的2线省会城市找了家开发公司做java的开发,前前后后做了1年半,...

snailclimb
2018/08/24
0
0
经过这么多次java面试,我明白了这么多道理

最近3个月一口气面了十几家公司的Java开发岗,大大小小的面试笔试加起来快20场,收获很多。本人毕业快2年了,毕业时在学校所在的2线省会城市找了家开发公司做java的开发,前前后后做了1年半,...

GeCoder
2018/09/11
0
0
两年工作经验幸运飞艇平台制作应该如何更好的面试

学习过程: 看了我的优劣势介绍幸运飞艇平台制作QQ2952777280【话仙源码论坛】hxforum.com【木瓜源码论坛】papayabbs.com,你会发现我的优势相对于我的劣势来说,简直不值一提。我自己对此也...

你的节奏
2018/07/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

关于对json的理解

下面是php代码 $data = [ "dataList"=>[ [ "id"=>0, "name"=>"名字1" ], [ "id"=>1, "name"=>"名字2" ] ] ]; echo json_encode($data,JSON_UNESCAPED_UNICODE); //输出结果 {"dataList":[{"i......

chenhongjiang
13分钟前
0
0
5.02-Navicat premium激活

http://www.downcc.com/soft/322714.html

静以修身2025
13分钟前
0
0
Qt类图表组件QtitanChart发布v6.0.0 beta 1|支持Qt 5.12

QtitanChart是一个包含多种控件的C++类库,能为您的应用提供漂亮、色彩鲜艳的图表。QtitanChart是基于Qt.C++实现的,支持所有主流的操作系统- Windows、Linux和Mac OS X。只需几行代码就可以...

FILA6666
13分钟前
1
0
宜人贷PaaS数据服务平台Genie:技术架构及功能

上篇:架构及组件 一、数据平台的发展 1.1 背景介绍 随着数据时代的到来,数据量和数据复杂度的增加推动了数据工程领域的快速发展。为了满足各类数据获取/计算等需求,业内涌现出了诸多解决方...

宜信技术学院
14分钟前
1
0
golang testify 测试库

项目日志 https://github.com/stretchr/testify

electricface
14分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部