关于面试:跳槽必看MySQL索引B树原理揭秘与索引优缺点分析
金三银四跳槽季,不晓得你筹备的怎么样了?前段时间我分享了两篇文章,粉丝股东们纷纷表示有用,有启发:,之前没看的话能够先看看: 程序员金三银四跳槽指南:工夫线&经典面试16问 这才动工没几天就收到喜报了,简历改了是真有用! 明天再给大家分享一下数据库索引的详解文章,这根本是必考的知识点。 一、索引介绍1、索引定义索引是存储引擎中,用于疾速找到记录的一种数据结构。索引可能帮忙存储引擎疾速获取数据,形象的说就是索引是数据的目录。 所谓的存储引擎,艰深的来说就是如何存储数据、如何为存储的数据建设索引和如何更新、查问数据等 技术的实现办法。 MySQL存储引擎有MyISAM、InnoDB、Memory,其中InnoDB是在MySQL 5.5之后成为默认的存 储引擎。 在理论场景中,索引对于良好的性能起到十分要害的作用。或者在数据量小且负载较低时,索引的不失当应用可能对性能的影响可能不会太显著,然而当表中的数据量越来越大的时候,索引对性能的影响就愈发重要,不失当的索引会让性能急剧的降落。 2、索引的查找形式在MySQL的InnoDB存储引擎中 若没有索引的状况下进行数据查问a) 在一个数据页中查问 当表中的记录比拟少时,所有记录能够寄存到一个数据页中。当查问记录时,依据搜寻条件的不同查问分为两种状况: 以主键为搜寻条件:在一个数据页内的记录会依据主键值的大小从小到大的程序组成一个单向链表。每个数据页都会为存储在它外面的记录生成一个页目录。通过主键查问某条记录能够在页目录中应用二分法疾速定位到对应的槽,而后再遍历该槽对应分组的记录,即可疾速找到指定的记录。以其余列作为搜寻条件:对于非主键列的查找,因为没有为非主键列建设对应的目录页,即未创立索引。无奈用二分法疾速定位相应的槽,只能从Infimum记录开始顺次遍历单向链表中的每条记录,而后比照每条记录是否合乎搜寻条件,即全表扫描,因而效率非常低。b) 在多个数据页中查问 在很多状况下,表中寄存的记录是十分多的,须要查问到的数据可能散布在多个数据页中,在多个页中查找记录能够分为两个步骤: 定位到记录所在的页从所在的页内查找相应的记录在没有索引的状况下,无论是依据主键列还是其余列的值查找,都不能疾速定位到记录所在的页,因而只能从第一页沿着双向链表始终往下找,因此十分耗时。 若存在索引的状况下进行数据查问在创立索引的状况下,每个数据页都会为存储在它外面的记录生成一个目录项,在通过索引查找某条记录时能够在页目录中应用二分法疾速定位到对应的槽,而后再遍历该槽对应分组中的记录,疾速找到指定的记录,确定记录后,即可向下寻找以后记录对应的下一个页节点,直到寻找到存在指标记录的叶子结点。 二、索引分类1、按数据结构分类Hash索引哈希表是一种以键-值(key-value)存储数据的构造,输出待查找的键,即key,就能够找到其对应的值,即value。 哈希的思路很简略,把值放在数组里,用一个哈希函数把key换算成一个确定的地位,而后把value放在数组的这个地位。 不可避免地,多个key值通过哈希函数的换算,会呈现同一个值的状况,即哈希碰撞,解决这种状况的一种办法是,拉出一个链表。 然而,在哈希表中,数据的存储不是按程序寄存的,所以哈希索引做区间查问的速度是很慢的。 所以,哈希表这种构造实用于只有等值查问的场景,比方Memcached及其他一些NoSQL引擎。 有序数组有序数组在等值查问和范畴查问场景中的性能就都十分优良。 在查找数据方面,有序数组能够通过二分查找的形式疾速找到,工夫复杂度是 O(log(N))。 同样,有序数组的索引构造反对范畴查问,通过二分法找到须要查找的范畴的首元素,而后向后遍历,直到找到第一个不满足条件的元素为止。 如果仅仅看查问效率,有序数组就是最好的数据结构了。然而,在须要更新数据的时候就麻烦了,往两头插入一个记录就必须得移动前面所有的记录,老本太高。 所以,有序数组索引个别实用于动态存储引擎。 B+树(InnoDB索引构造)在MySQL 5.5之后,InnoDB成为默认的MySQL存储引擎,B+Tree索引类型也是MySQL存储引擎采纳最多的索引类型。 在InnoDB数据页中,各个数据页能够组成一个双向链表,而每个数据页中的记录会依照主键值从小到大的程序组成一个单向链表。 在介绍B+树时,咱们以主键索引为例,来看看InnoDB是如何构建主键索引的B+树。其余字段所建设的索引与主键索引类似,只是将主键字段替换成指定的索引字段来构建B+树。 主键策略在创立表时,InnoDB存储引擎会依据不同的场景抉择不同的列作为主键索引: 如果有指定主键,默认会应用主键作为聚簇索引的索引键如果没有指定主键,则抉择第一个不蕴含NULL值的惟一列作为聚簇索引的索引键在下面两个都没有的状况下,InnoDB将主动生成一个隐式自增id列作为聚簇索引的索引键除主键索引外,其它索引都属于辅助索引(Secondary Index),也被称为二级索引或非聚簇索引。创立的主键索引和二级索引默认应用的是B+Tree索引。 建设B+树索引的条件条件一:下一个数据页中记录的主键值必须大于上一个数据页中记录的主键值 咱们晓得,在MySQL中,新调配的数据页编号可能并不是间断的,即这些数据页在磁盘上并非紧挨着存储。须要通过保护上一下和下一页的编号,因而,在InnoDB中,每个数据页组成了一个双向链表来保护每个数据页之间的高低关系。 为什么构建B+树须要满足条件一呢? 起因在于为了进步范畴查问的效率,B+树要求叶子节点中的数据记录依照主键值的程序进行排列。 当进行范畴查问时,如果叶子节点中的数据记录不依照主键值的顺序排列,就会减少查找的复杂度。如果下一个数据页中记录的主键值小于上一个数据页中记录的主键值,那么在进行范畴查问时就须要在不同的叶子节点之间来回跳转,这样会减少IO操作次数和查问工夫。 因而,为了保障范畴查问的效率,B+树要求叶子节点中记录的主键值必须依照顺序排列,即下一个数据页中记录的主键值必须大于上一个数据页中记录的主键值。这样能够确保在进行范畴查问时能够顺利地依照主键值的程序进行遍历,进步查问效率,同样MySQL中的预加载页性能也能够缩小IO操作次数。 在InnoDB中,在对页中的记录进行增删改操作时,必须通过一些记录挪动的操作来始终保障:下一个数据页中用户的记录的主键值必须大于上一个页中用户记录的主键值,则这个过程也成为页决裂操作,即在一个数据页中插入记录,而该数据页在插入之前曾经满了,则须要申请一个新的数据页,而后移动局部数据过来。 条件二:须要给所有的数据页建设一个目录页 因为每个数据页的编号可能并不间断,因而须要为这些数据页建设一个目录。 比方当咱们看一本书的时候,书的目录能够帮忙咱们疾速定位到咱们想看的内容,而目录题目对应的页号能够比作每个数据页的页号,通过书的目录咱们能够疾速定位到咱们想看的内容,同样的情理,通过为数据页建设目录,在目录中存储数据页的编号,即可通过目录疾速定位到相应的数据页。 目录页能够包含两个内容: 数据页的记录中最小的主键值,用key示意数据页页编号,用page_no示意为了不便阐明,咱们能够定义一个数据表: CREATE TABLE `index_demo` (`a` int NOT NULL,`b` int DEFAULT NULL,`c` char(1) DEFAULT NULL,PRIMARY KEY (`a`)) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci ROW_FORMAT=COMPACT;上述表定义中,应用了COMPACT行格局来存储数据,COMPACT行格局的简化存储如下: ...