深入理解索引B+树的基本原理

目录1. 引言2. 为什么要使用索引3. 索引的概述4. 索引的优点是什么4.1 降低数据库的IO成本提高数据查找效率4.2 保证数据库每一行数据的唯一性4.3 加速表与表之间的连接4.4 减少查询中分组与排序的执行时间5. 索引的缺点是什么5.1 创建索引和维护索引非常耗费时间5.2 索引也是占用磁盘空间的5.3 索引会降低表的更新速度6. B 树到底是什么样的7. 数据库底层存储数据的实质8. 索引的实现原理9. 为什么B树的高度不建议超过四层10. 什么是聚簇索引10.1 聚簇索引的特点10.2 聚簇索引的优点10.3 聚簇索引的缺点10.4 聚簇索引的补充说明11. 什么是非聚簇索引12. 什么是回表13. 为什么非聚簇索引的叶子节点不存储一份完整的数据方便查找呢14. 聚簇索引与非聚簇索引的区别15. 什么是联合索引1. 引言我们知道只要谈起数据库索引重中之重不管你是面试开发程序员架构师还是校园招聘你会发现几乎都会问到索引。那么它到底是个什么东西竟能如此重要它到底有什么好处呢为什么面试的时候总喜欢问索引呢它的底层实现是什么样的呢今天我们就一同来揭晓这些问题的答案。想要更加透彻深入的学会索引建议同学们对数据结构有一些基本的了解特别是普通二叉树平衡二叉树红黑树哈希表B树B树了解这些数据结构对我们了解索引是有一定帮助的。如果不太了解也没有关系可以先随着小编的讲解慢慢理解多看几遍这些都是比较偏理论和底层的东西主要靠理解。2. 为什么要使用索引我来说一个场景假设现在我的一张用户表中有十万条用户数据用户 id 唯一我想要查询id 位80000的用户信息那么数据库是靠什么快速的在十万条数据中找到这条id为80000的用户数据的呢各位有没有想过这个问题其实底层就是索引在帮忙做一个简单的比喻如果我们把刚才的用户表中的数据存放到一本字典中那么索引就是这个字典的目录当我们想要查找某一个数据的时候数据库底层不会傻乎乎的去一页一页从字典中翻找我们想要的数据而是直接去翻这根本字典的目录通过目录精准定位我们想要查询的数据在哪一页然后直接定位到那一页将我们要查找的数据取出。那么各位再想一下如果字典没有目录。会是什么样的结果呢我们要查找用户张三的信息然后数据库受到了指令从第一页开始翻看查阅没有翻到第二页有没有翻到第三页......各位想过没有这会多麻烦所以通过字典目录提高查找效率是必须要做的通过索引查找数据也是迫在眉睫的但同样我们既然制造了目录如果我们对字典中的数据做了更改目录是不是也要改啊这就为我们后续索引的缺点做了铺垫。总结来说就一句话之所以要使用索引是因为索引可以提高我们查找数据的效率。3. 索引的概述MySQL官方给索引的定义是索引(Index)是帮助MySQL高效获取数据的有序的数据结构。简洁点来说索引的本质是数据结构。此外索引是在存储引擎中实现的当我们的存储引擎不同时索引底层的数据结构也不相同。同时存储引擎中还定义了一个表中最多不能超过16个索引但其实我们也用不到这么多所以完全可以放心也定义了索引的长度不能超过256个字节其实也很大了我们通常不会把索引定义那么大也可以放心。4. 索引的优点是什么4.1 降低数据库的IO成本提高数据查找效率各位细想我们的数据都是存储在磁盘上的只有我们在需要的时候才会从磁盘IO读取到内存中。如果没有索引当我想要查找某条数据时我会就会先从磁盘IO加载第一页的数据到内存(不理解什么是数据页可以暂且理解为一部分数据表中的数据在磁盘中是分页存储的每个数据页大小为16KB)然后遍历数据发现没有找到再经过IO磁盘加载第二页的数据到内存再遍历查找...... 各位知道内存中数据的处理速度是很快的但是从磁盘加载到内存这个速度就很慢了假设我们遍历一页数据需要1ms那么IO一次可能就需要50ms这还只是加载了第一页的数据那如果有很多很多页数据查找速率绝对非常慢。但是如果我们使用了索引我们只需要IO一次将索引加载到内存中遍历索引精准找到数据所在的页数然后第二次IO直接读取是数据所在的那一页数据这样的话只需要经过两次磁盘IO就可以得到我们需要的数据了。4.2 保证数据库每一行数据的唯一性我们知道表中通常都是有主键的而且都会设置为非空且唯一我们的索引也是一样主键默认就是索引即主键索引还有非主键索引。主键(索引)唯一且非空就保证了数据库每一行数据的唯一性。4.3 加速表与表之间的连接对于有父子关系的子表与父表在进行联合查询或存在外键关联的表联合查询时索引可以加速表与表之间的连接从而提高表的查询效率。举个例子user 用户表有 user_iduser_name等字段user_id 默认为主键字段(主键索引)order 订单表order_iduser_id等其他字段order_id 默认为主键字段(主键索引)此外再给 user_id 添加普通索引下面当两张表通过 on 关联查询时我们就不需要全表扫描 order 表而是根据 user 表的 user_id 再根据索引精确查询匹配提高表的连接查询速度select u.* from user u left join order o on u.user_id o.user_id4.4 减少查询中分组与排序的执行时间各位想一下字典中的目录我们都是按照一定的规律去进行排列的索引也是一样的道理从小到大或从大到小把数据进行规律排列既然是已经排好序的数据了当我们在查询语句中对数据进行 ORDER BY 排序时候其实已经是有序的了那么就省去了我们再次排序的时间降低了CPU的消耗而且以后查询排序都不需要再去浪费时间是一个一劳永逸的做法。5. 索引的缺点是什么5.1 创建索引和维护索引非常耗费时间这一点我想不难理解各位想当我们对一本书中的内容做了更改之后你是不是也要去更改目录啊特别是你的书内容如果比较多如果你删除了几页内容其他的内容都要跟着做调整如果你一直往书中继续写内容目录也要跟着增多吧所以说索引的创建与维护也是非常浪费时间的5.2 索引也是占用磁盘空间的我们还把数据的内容比作是一本书中的内容书中的内容需要用纸张去记录同样目录也要写在纸上而且索引本身就是数据结构是需要占用磁盘的空间的并且随着数据量的增大而增大。5.3 索引会降低表的更新速度其实这一点与维护索引是有一些内在关联的如果我们对表中的数据做了动态修改那么索引也是会不断地去动态修改维护的这就大大的降低了表的更新速度。6. B 树到底是什么样的我们知道树是一种常见的数据结构我们最常见的就是二叉树还有平衡二叉树还有二叉树的升级版红黑树。既然有二叉树就有三叉树N叉树。其实B树底层就是一个N叉树这里我以三叉树为例模型如下图所示我们的最顶层就是根节点中间层是子节点最下层是叶子节点。在数据库底层 InnoDB 存储引擎中存储数据和索引就是采用B树的形式存储的。7. 数据库底层存储数据的实质如上图所示是我们数据库中常见的一张表这里有很多的数据但是在底层表的每一行数据都是单独存储的在磁盘上的存储位置不一定是连续的。因为如果我们表中的数据有很多达到了上万条数据那么在磁盘中不一定有那么大的一个连续空间因此在数据库底层它的每一行数据都是单独存储的而且还要满足一个逻辑上的连续我们 employee_id 100 的员工下一条记录是 employee_id 101 的员工这一点是不能变的不能说我查一次它们的顺序就变一次一定要它们保持一定的逻辑连续性。说到这里各位应该就明白了吧没错就是链表其实表中的每一行数据在磁盘底层是采用单向链表的形式来存储的这样不仅解决了存储空间大小不够问题还解决了让它们在逻辑上满足连续性的问题。就拿上面这张表举例在数据库的底层employee_id 100 的员工就是链表的头节点它内部还会存储 employee_id 101 的员工的地址值从而找到该员工的全部相关信息而employee_id 101 的员工内部也会存储 employee_id 102 的员工的地址值通过该地址值找到 employee_id 102 的员工全部信息由此形成一个单向链表。8. 索引的实现原理如上图根据上面B树的结构我们就能大致推演出索引的底层原理了这里我化繁为简简单说明。我们先看最下层最下层也是叶子节点页这些叶子节点页之间是使用双向链表进行连接的而内部的数据则是我刚刚说的通过单向链表连接的图中已经标识出而且每一页中都有一个数组存放主键的值方便我们后续使用二分法快速确定要查找的数据。在B树索引中所有的真实数据都是存放在叶子节点叶中的如图在叶子节点中页10中下方的 14u39d44a 就是一条条真实的数据上方的0就是标记这些是数据假设134这些首字段为一条条数据的主键。我们继续推演如果没有中间层页30与页32只有最下方一层当我们想要找想要查找主键为100的用户信息时就需要从页10开始从头遍历这个双向链表在遍历到页9的时候找到了主键为100的用户我们直接获取到该用户的信息一共遍历了3页需要进行三次磁盘IO。如果我们加上中间层为每一个叶子节点页再创建一个目录即页30与页32页30下方存储了11052812920920四条数据。这里的110中的1指代的就是叶子节点页10中最小的一条数据110则是指代页10实际存储的是页10的内存地址528则是叶子节点页28中的最小主键值5与该页所在的地址值这些数据上方都是1表示他们仍然是目录页而不是真实的数据...... 我们使用了这个中间目录页之后我们再去获取主键为100的用户数据时就会先去遍历中间页在中间页中确定主键值为100的用户数据存放在页9中就可以直接将页9中的数据全部读取到内存然后再去寻找该用户的数据可以发现此时加上了中间页之后只需要两次IO节约了时间提高了查找效率。我们继续类比推理如果以后我的数据越来越多中间也最多只能存放四个叶子节点页的数据再多就存不下了这个时候我们就需要继续创建新的中间页而如果中间页一直增多就会面临和刚才叶子节点页一样的问题。这个时候我们就可以套娃式的去再创建一个中间页的顶层也让这个顶层页使用类似的手段存放中间页的重要数据。举例说明我们想要查找主键为300的用户数据第一次磁盘IO我们把页33的全部数据加载到内存中经过二分查找判断发现与主键为300的用户数据应存放在子页30中在然后进行第二次IO将子夜30的全部数据加载到内存中再经过二分查找判断确定主键为300的用户数据存应放在叶子节点页20中在进行第三次磁盘IO将叶子节点页20中的数据全部加载到内存中再经过二分查找快速定位到主键为300的用户所在的内存地址获取到信息此时只需要经历三次磁盘IO而且非常稳定当我们想要查询某条数据是都是进行三次磁盘IO就可以获取到结果找得到或找不到都要返回极大的保证了我们查找数据时的稳定性。9. 为什么B树的高度不建议超过四层在刚才我举得例子中各位应该看得出来我所举例的B树是三层绝大多数情况下都是三层最多四层。而在面试的时候有些面试官会问你为什么B树的不建议超过四层请给出具体的原因。原因如下不知道各位发现了没有当我们的B树只有两层时我们最多就可以经过两次磁盘IO就可以查找到数据当B树是三层时我们进行三次磁盘IO就可以获取到数据。这也从侧面印证了一点我们与磁盘交互的次数是受到B树高度的影响的各位都知道内存中处理数据速度是非常快的二分查找数据可能就1ms~3ms左右的时间而与磁盘IO就不一样了磁盘IO一次可能就需要花费100ms每交互一次100ms这个效率是非常低的因此我们应当尽量减少与磁盘的IO次数这就要求我们B树的高度不能过高最好三层不能超过四层。那肯定会有人问问什么非要是三层或四层我选五层不行吗其实从原则上来讲也是可以的但是我们还要考虑数据的存储量这里给各位说一下数据库的底层一个真实的数据页大小是16KB也就是 16000 个字节假设我们的每条数据占用160个字节160个字节已经不小了完全够用那么我们每个叶子节点页就可以存储 16000/160 100 条数据。而我们的非叶子节点页因为并没有存储真实的用户数据所以可以存储更多的内容假设我们的目录页可以存储 1000 条叶子节点页数据当我们的B树正好满两层的时候存储的数据量是 100 * 1000 100,000 十万条数据当我们 B 树满三层时存储的数据量是 100 * 1000 * 1000 100,000,000 一亿条数据让我们的B树满四层时存储的数据量是 100 * 1000 * 1000 * 1000 100,000,000,000 一千亿条数据可以看到当B树四层的时候数据量已经非常恐怖了而且我们也不可能在一张表中存储这么多数据。而在实际开发业务的时候我们会采用微服务的架构并对数据库进行分库分表进行读写分离不会让大量数据在同一张表中存储既不安全效率又低。因此我们通常会把B树控制在三层左右此时一张表就足以存储一亿条数据而且只需要三次磁盘IO就可以查找到想要的数据综合考虑是最优的选择。如果像阿里京东腾讯这些用户量多余1亿的企业也有可能会采用四层B树但其实还是是很少这么做的。这就是为什么要把B树的高低控制在四层以下总的来说就一句话三层或四层B树既满足了数据量的存储需要又达到了最佳查找效率。10. 什么是聚簇索引聚簇索引又名主键索引它是基于表的主键而生成的索引而且它不是一种索引的类型而是一种数据的存储方式(表中所有的用户数据都会存放在叶子节点中)如下图所示就是一个经典的聚簇索引。在 InnoDB 引擎中聚簇索引是不需要我们手动创建的在我们创建好表结构的时候数据库的底层已经为我们生成聚簇索引并随着我们数据的添加索引会一直不断的变化和维护。10.1 聚簇索引的特点聚簇索引还有一些特点只有满足以下四点的索引才能称为聚簇索引1. 每个页内的记录是按照的主键的大小顺序形成的一个单向链表例如页10中的14u与39d便是通过单向链表连接的2. 各个存放的数据页之间采用的是双向链表进行连接如图中的页10与页28之间就是双向链表3. 存放目录项记录的页(即刚才我所提的中间层)它们之间也是采用双向链表的形式进行连接如图中的页30与页32就是双向链表4. B 树中存放的是完整的表数据如图中页10的14u39d等这里我列的简单只有三个字段实际聚簇索引存储的数据会以你定义的表中的字段为主10.2 聚簇索引的优点1因为聚簇索引中将索引与所有的表数据都存储在了B树种所以聚簇索引比非聚簇索引查询效率要高2因为聚簇索引是基于主键大小排列的索引所以对于主键的范围查找与排序查找速度非常快3因为聚簇索是引按照一定的顺序进行排列再查询显示一定范围的数据的时候由于数据是紧密相连的数据库就不需要从不同的区块中去提取数据节省了大量的IO操作。10.3 聚簇索引的缺点1插入的速度严重依赖于插入的顺序。因为聚簇索引是按照逐渐的顺序去建立的如果我们不按照顺序去插入而是突然插入一个主键值大的数据又突然插入一个主键值小的数据这就会导致索引会不断地去动态变化还可能出现页分裂严重影响性能因此对于 InnoDB 引擎来说建议在插入数据的时候按照顺序插入或者使用主键自增策略。2更新主键的代价极高。因为聚簇索引就是基于几件生成的如果我们对主键做出更改那么整个索引结构可能都要进行更改而进行更改是非常耗费性能的因此对于 InnoDB 引擎来说我们一般最好把主键定义为不可更改。10.4 聚簇索引的补充说明1MySQL 数据库目前只有 InnoDB 引擎支持聚簇索引MyISAM 引擎不支持聚簇索引2由于数据物理存储排序方式只有一种所以每个 MySQL 表只能有一个聚簇索引一般情况下都是该表的主键3如果我们没有给表定义主键那么 InnoDB 会选择一个非空且唯一的字段替代如果也没有这样的字段那么 InnoDB 会隐世式定义一个主键作为聚簇索引4为了充分利用聚簇索引的特性 InnoDB 引擎下在定义表的主键的时候不建议使用无序的id例如UUIDMD5HASH字符串等作为主键否则无法保证数据的顺序增长。11. 什么是非聚簇索引非聚簇索引也可以叫二级索引或叫辅助索引。刚才我们说到了聚簇索引是 InnoDB 引擎基于主键自动生成的可以提高有关主键的查找速度和查找范围也就是说只有搜索条件中包含主键字段时才有效果。那么当我们不使用主键字段来查找数据而是基于普通字段查找数据同时又想提高查找效率的时候我们就可以通过普通字段定义非聚簇索引。如下图所示就是一个非聚簇索引所构成的 B 树。这里需要注意一点非聚簇索引构成的 B 树与聚簇索引构成的 B 树稍有不同。这里目录页44与子目录页4243的原理与聚簇索引中类似但叶子节点中就不一样了刚才我说到了聚簇索引中存放着完整的表数据而在非聚簇索引中叶子节点中只存放着索引对应的那个普通字段与主键值。如图中蓝色对应的就是普通字段黄色对应的就是主键值我们可以看一下在前面那张图中页9中存放这一条数据202e正好对应着我们这里的非聚簇索引这里页34下面蓝色方块中值为2的数据对应的主键值也为20即220。这样说各位同学应该更好理解一些各位可以将上图与前面聚簇索引中的字段值做对比就可以看出来我就不一一举例说明了。12. 什么是回表刚才我说到了在非聚簇索引中叶子节点只存放了该索引字段的相关信息和主键信息那么只有这两项信息肯定是不够的如果我们的目的是通过非聚簇索引查询某条用户的全部信息它就会进行回表操作什么是回表呢其实很简单当我们使用非聚簇索引的字段作为查询条件去查询表中的相关信息时数据库会先根据非聚簇索引形成的 B 树查询到该字段对应的主键值再根据主键值去聚簇索引形成的 B 树中查询完整的用户信息。这个过程中需要先查询非聚簇索引的 B 树再去查询聚簇索引的 B 树这个过程就叫做回表。举个栗子现在有一张表 user 主键 uid 手机号码 phone用户名 username密码 password四个字段我们给手机号码字段创建了非聚簇索引那么它的底层就会只存储手机号码信息和所对应的主键uid 信息当我们通过 手机号去查询用户完整信息时语句应该是 SELECT * FROM user WHERE phone 待查询用户手机号在这个查询语句中它会先去非聚簇索引形成的 B 树通过 phone 查找到对应的主键uid查找到主键uid的信息之后它会再去聚簇索引的 B 树中通过 uid 查询出完整的用户信息并返回这就是它在底层的执行逻辑先查非聚簇索引再回表查聚簇索引。13. 为什么非聚簇索引的叶子节点不存储一份完整的数据方便查找呢这个问题其实也算是一个面试题。我刚才说了什么是回表但是不知道各位发现一个问题没有回表还需要再查寻一次 B 树这样不是很麻烦吗我们直接将用户的全部信息在非聚簇索引的 B 树中叶存储一份多省事啊怎么不这样做呢如果你也有这样的问题说明你认真思考了。大家想一想在聚簇索引中我们已经存储了一份完整的表数据还有 B 树的结构这些都是非常占用磁盘满空间的而非聚簇索引又不止可以创建一个我们可以创建多个刚才我举的例子中只有四个字段在实际的业务场景中二十个字段也是很有可能的如果我们为了方便查找又创建了三个非聚簇索引并且图方便在非聚簇索引中也存储完整的用户数据各位同学想一想这样是不是非常冗余我们的用户数据明明存储一份就够了但是你创建一个非聚簇索引数据就多存储一份再创建一个再存储一份我们创建三个非聚簇索引那么加上聚簇索引我们底层的数据足足存储了四份非常非常冗余这是绝对不允许的。另外如果我们把全部的数据都存在非聚簇索引中那么当我们要对用户数据作出修改时有多少个索引我们就要修改多少次各位想是不是我们对用户张三做修改所有的索引中关于张三的信息都要做修改非常不划算不值得。所以不在非聚簇索引上也存储一份完整的用户数据一方面是为了防止数据大量冗余造成磁盘资源的浪费另一方面是防止多余的操作。14. 聚簇索引与非聚簇索引的区别1聚簇索引叶子节点存储的是完整的用户数据而非聚簇索引中存储的只有主键与索引字段数据非聚簇索引不会影响表的物理存储结构2一个表只能有一个聚簇索引但是可以有多个非聚簇索引3使用聚簇索引时查询效率很高但如果是对数据进行增删改操作效率会比非聚簇索引低15. 什么是联合索引说的准确一些联合索引其实属于是非聚簇索引中的一种它与我们说的联合主键是有一些类似的刚才我们说的非聚簇索引是使用一个字段构成 B 树而有些时候我们会把数据库中的两个字段都作为索引这种情况下形成的索引就叫联合索引。举个例子假设一张学生表 student 有主键字段C1非主键字段C2C3C4C5。现在我们为C2与C3创建联合索引那么形成的 B 树中就会存放 C2C3C1字段并按照从上到下的顺序排列会先比较联合字段C2的大小先按C2大小排序当C2大小相同时再根据C3大小排序在下方存贮主键C1的值从而形成一个联合索引 B 树。