IT评测·应用市场-qidao123.com技术社区

标题: 数据库索引底层数据结构之B+树&MySQL中的页&索引分类【纯理论干货，口试必 [打印本页]

---

作者: 李优秀    时间: 2024-9-21 13:32
标题: 数据库索引底层数据结构之B+树&MySQL中的页&索引分类【纯理论干货，口试必
目录
1、索引简介
1.1 什么是索引
1.2 使用索引的原因
2、索引中数据结构的设计 —— B+树
2.1 哈希
2.2 二叉搜刮树
2.3 B树
 2.4 最终选择之——B+树
2.4.1 B树与B+树的对比(面向索引)【口试题】
3、MySQL中的页
3.1 页的使用原因
 3.2 页的结构
3.2.1 页文件头和页文件尾
 3.2.2 页主体
3.2.3 页目录
3.2.4 数据页头
4、B+树在MySQL索引上的应用
 4.1 三层树高的B+树的数据存储量(理论上)
5、索引的分类
5.1 主键索引
5.2 平凡索引
5.3 唯一索引
5.4 全文索引（相识）
5.5 聚集索引
5.6 二级索引/非聚集索引
5.7 索引覆盖

---

1、索引简介

1.1 什么是索引

MySQL中的索引是一种数据结构，它可以高效快速的查询、更新相应数据，大大的提高开发服从。索引通过⼀定的规则分列数据表中的记录，使得对表的查询可以通过对索引的搜刮来加快速度。
我们可以将索引理解为书中的目录，可以根据目录快速的锁定到我们要阅读的页数。
1.2 使用索引的原因

 数据库之以是叫数据库，那么MySQL的设计一定需要满足两个需求：

• 安全
  
• 服从
  

 显而易见，使用索引的原因只有一个：提高查询服从。

---

2、索引中数据结构的设计 —— B+树

 索引的出现就是为了提高查找服从，那它底层到底使用的是哪种高效的数据结构呢？让我们继承探索。
2.1 哈希

说到高效查找 ，相比各人第一个想到的就是哈希表，因为它的时间复杂度可以到达O(1)级别，可谓是极其高效，正因为其高效的查找性能也使哈希成为最重要的数据结构，没有之一。但是由于哈希只能一个数据一个数据的查找，不具备范围查找的功能，故索引并没有使用哈希作为它的底层结构。
2.2 二叉搜刮树

二叉搜刮树中序遍历得到的是一个有序序列，这使得其具备范围查找的功能。
但是，二叉搜刮树在极端情况下大概为退化成一棵单分支树，时间复杂度也会退化为O(N)。

并且在数据过多的情况下，无法控住树高，由于数据库上的数据是在磁盘上保存的，而每访问一个节点都会发生一次磁盘IO，磁盘的访问速度是很慢的，以是当搜刮二叉树出现单分支形态时，将严峻拉低数据库性能。
   由此得出：磁盘IO是制约数据库性能的主要因素。【拓展】
  故索引也没有使用二叉搜刮树作为它的底层结构。
2.3 B树

B树仍具备中序遍历序列有序的特点，在B树中，每个节点可以有多个子节点(可以超过2个)。对于N阶B树(度/阶)，一样平常来说其子节点个数不可>=N个，当插入的节点为第N个孩子时，将开发另一条分支。
由于其可以有多个孩子节点，故其可以有用的控制树高，时间复杂度也稳定为O(logN)，这也意味着将会低落磁盘IO开销，提拔数据库性能。

 2.4 最终选择之——B+树

上面提到B树不仅可以满足数据库范围查询的要求，而且可以低落IO开销，但是开发数据库的大佬并没有将B树作为索引的底层结构，因为他们发现了更加高效更加得当的数据结构——B+树。
B+树在满足B树可控树高、高效O(logN)查询、... 的优秀性能下，进一步做了优化。
2.4.1 B树与B+树的对比(面向索引)【口试题】

 1.B+树的叶子节点间使用单链表毗连，可以通过一个叶子节点找到它相邻的兄弟节点

• 且MySQL在组织叶子节点时，使用的是双向循环链表
  

2.B+树中，所有节点的值都包含在了叶子节点中

• 在MySQL中，非叶子节点只保存了对子结点的引用，并不保存真实数据，所有的真实数据都保存在叶子节点中。因此，对于B+树而言，在雷同树高的情况下，查询恣意元素的时间复杂度都是雷同的，性能均衡。
  

---

3、MySQL中的页

3.1 页的使用原因

MySQL中，使用innodb存储引擎后生成的表空间文件后缀都为.ibd。而在.ibd文件中，最重要的结构体就是页(Page)，页是内存与磁盘交互的最小单位，默认大小为16KB。
show variables like 'innodb_page_size'; #检察页大小，单位字节

每次内存与磁盘的交互至少读取一页，以是在磁盘中每个页内部的地点都是连续的。之以是这样做有以下两点原因：

• 时间局部性：如果⼀个信息项正在被访问，那么在近期它很大概还会被再 次访问
  
• 空间局部性：未来要使用的数据大概率与当前访问的数据在空间上是邻近的
  

以是根据局部性原理， 以⼀次从磁盘中读取一页的数据放入内存中，当下次查询的数据还在这 个页中时就可以从内存中直接读取，从而减少磁盘I/O，提高性能。
注意：即使一个页中没有数据，也会使用16KB的存储空间。同时与索引的B+树中的节点对应，也就是说，索引树中的每一个节点，就对应一个页。

 3.2 页的结构

在MySQL中有多种不同范例的页，最常用的就是用来存储数据和索引的"索引页"，也叫做"数据 页"，但岂论哪种范例的页都会包含页头(File Header)和页尾(File Trailer)，页的主体信息使用数 据"行"举行添补。
每创建一个表，生成一个保存数据的文件，即.ibd文件，也称为独立表空间文件。
上文说到，一个.ibd文件中，最重要的结构就是页，接下来，让我们一起探究页的组成结构。

3.2.1 页文件头和页文件尾

页文件头和页文件尾中，包含了当前文件的主要信息：

这⾥我们只关注，上一页页号和下一页页号，通过这两个属性可以把页与页之间链接起来（通过页号和页大小，可以计算出上一页和下一页在磁盘上的偏移量），形成⼀个双向循环链表。 
 3.2.2 页主体

页主体部门是保存真实数据的主要区域，每当创建⼀个新页，都会自动分配两个行。

• ⼀个是页内最小行 Infimun
  
• ⼀个是页内最大行 Supremun
  

这两个行并不存储任何真实信息，而是作为数据行链表的头和尾。
并且，每一个数据行有一个记录下一行的地点偏移量的区域：next_record，故此，页内所有数据行组成了⼀个单向链表。

 当向⼀个新页插入数据时，将 Infimun 毗连第一个数据行，最后一行真实数据行毗连 Supremun ，这样数据行就构建成了一个单向链表，更多的行数据插入后，会按照主键从小到大的次序举行链接，自动排序。
也就是说，所有数据行间形成单向链表：最小化Infimun始终为链表的头，最大行Supremun始终为链表的尾。

3.2.3 页目录

上文提到，页中的每个数据行间形成了一个单向链表，但是单链表的时间复杂度为O(N)，无法满足高效查询，为了提高查询服从，InnoDB采用二分查找，以参加页目录的结构来解决查询服从问题。
页目录实现情势：将页内包括头行(最小行Infimun )、尾行(最大行Supremun )在内的所有行举行分组。具体实现如下：

• 最小行单独为一组
  
• 其他每个组最多8条数据，超过8条数据时会开发出一个新的分组
  
• 最大行永久在最后一个分组中
  
• 每创建一个分组，页目录就会创建一个槽，即槽的数量与组的数量是同等的，且每个分组与槽都一一对应
  
• 槽中记录了其对应分组的最后一条记录的地点，同时记录这条记录的主键值
  

经太过组和槽的创建，查找操作时就可以或许以二分查找性能快速定位到要目的数据，大大提高了查找服从。
例如，我们要查找某一条存在的记录：

• 第一步，通过索引树找到该记录地点页。
  
• 第二步，通过槽找到该记录地点分组。(每个槽都记录了该分组最后一条记录的主键值和地点，因为页中所有数据行通过主键有序分列，通过比力槽中的主键值，可快速定位到目的记录地点分组)
  
• 第三点，遍历该分组的单链表(最多只有8条数据)，查找成功。
  

   注意：页与页(节点与节点)间的遍历是从磁盘中加载数据的，要想查询页中的的内容需要先通过磁盘IO把页从磁盘加载到内存中（先加载后访问）。 
  3.2.4 数据页头

数据页头记录了当前页保存数据相干的信息。

---

4、B+树在MySQL索引上的应用

在索引的B+树的叶子节点和非叶子节点中：

• 非叶子节点和叶子节点均为页，称为索引页/数据页。
  
• 非叶子节点只记录索引信息。在索引页中保存的是主键值和叶子节点的引用。
  
• 叶子节点存储的是真实的数据。数据页保存的是具体的数据。
  
• 最后一层的叶子节点中，页与页之间通过页号建立起关联关系(页号信息在页头中存储)，最终形成了一个双向循环链表。
  

例如查找id为5的记录：

• 判断B+树根节点的索引记录，5<7，进入左孩子节点，找到索引页2
  
• 判断索引页2的索引记录，找到与5相称的记录，命中
  
• 进入数据页3
  

 故以上过程共经过3次IO过程：加载索引页1-->加载索引页2-->加载数据页3
 4.1 三层树高的B+树的数据存储量(理论上)

上文已阐明，一个页的大小为16KB。

• 第一层：根节点（索引页）
  

一个索引页存储的是主键值和子节点的引用。假设主键值占8Byte，地点占6Byte，故一条索引记录的大小为8+6=14Byte。故一个索引页可保存16*1024/14=1170条索引记录。故B+树的根节点可保存1170条索引记录，即可指向1170个子节点。

• 第二层：非叶子节点（索引页）
  

同样，第二层的每个索引页可指向1170个子节点(数据页)。

• 第三层：叶子结点（数据页）
  

算上页中页头、页尾、页主体....等结构空间的占比，假设一个页中最多可以保存16条记录。故，三层树高的B+树一共可存储 1170*1170*16=21,902,400条记录。
综上，三层树高的B+树一共可存储 1170*1170*16=21,902,400条记录，而在存储这么多数据的情况下，只需要经过3次IO就可以查询到目的数据（加载索引页1-->加载索引页2-->加载数据页3），可以说是极其高效。
而且，如果将索引页1、索引页2加载到内存中举行缓存，那么只需一次IO就可以查询成功，服从极高。

---

5、索引的分类

5.1 主键索引

• 主键索引也叫做聚集索引、聚簇索引
  
• 当在表中定义一个主键(PRIMARY KEY)时，将自动创建主键索引，索引中的值就是主键列的值，故猛烈建议为每一个表定义一个主键。
  
• 主键索引树中存储了所有的数据。‌
  

主键索引树，特别是InnoDB存储引擎的主键索引，其设计使得所有数据都存储在主键索引上。当使用主键举行查找时，服从非常高，因为只要找到主键，就代表找到了该行记录。这种设计使得主键索引成为查找数据的一种非常高效的方式。
5.2 平凡索引

• 平凡索引是需要手动创建的索引。
  
• 最根本、最常用的索引范例，没有唯一性限制。
  
• 为了提拔查询服从，工作中通常为查询频仍的列创建索引。
  
• 可以为多个列创建组合索引，称为复合索引或组合索引。
  
• 创建索引的条件是：列的值重复性不高。例如：gender(性别)列，该列值要么为1(男)，要么为2(女)，就没有须要创建索引。
  
• 创建索引之后都会生成一棵索引树，创建多少索引就会生成多少棵索引树。
  

   注意：
  创建索引所生成的索引树也是会占用磁盘空间的。
  以是，在创建索引时，肯定要慎重思量需不需要创建。
  索引树越多，对增、删、改的服从影响越大，将会拉低数据库性能。
  以是没有须要创建冗余索引(如上文的gender列)。
  5.3 唯一索引

• 当表中定义有UNIQUE唯一键时，将自动创建唯一索引。
  
• 与平凡索引范例，但唯一索引的列不允许有重复值。 
  

5.4 全文索引（相识）

• 基于文本列(CHAR、VARCHAR或TEXT列)上创建，以加快对这些列中包含的数据查询和DML操作
  
• 用于全文搜刮，仅MyISAM和InnoDB引擎支持。
  

5.5 聚集索引

• 即上文提到的主键索引。
  
• 如果表中没有定义主键(PRIMARY KEY)，innoDB将使用第一个UNIQUE和NOT NULL的列作为聚集索引（聚集索引可以标识数据行的唯一性）
  
• 如果表中没有主键大概唯一非空列作为符合的聚集索引时，innoDB会自动新增ROW_ID列，ROW_ID单调递增，并使用ROW_ID作为索引。（ROW_ID为数据行中的隐藏列之一，我们查询不到，也使用不了）
  

5.6 二级索引/非聚集索引

• 聚集索引以外的索引称为非聚集索引或二级索引
  
• 二级索引中的每条记录都包含了该行的主键列（默认包含的），以及二级索引指定的列（一列或多个列）。
  
• 要查询的列，没有被索引完全包含（索引中的列不敷），这时InnoDB通过二级索引的索引树查询到主键值，再使用主键值通过主键索引树查询相干记录，这个过程称为回表查询(平凡索引树 --> 主键索引树)。
  
• 如果要查询的列，在二级索引中刚好就有（二级索引包含了要查询的列），那么此时不需要回表查询，可以直接从二级索引树中把数据返回给用户，这种情况称为索引覆盖。
  
• 创建复合索引时，如果name列在sn列的前面，则使用where条件时，也要先使用name再使用sn，也不能只使用sn(使用AND时，两列次序不作要求)。如果只使用sn列，那么索引失效(不走索引)。如果非要使用sn列来条件查询，可以为sn单独创建一个索引。可以这样理解：查字典时，必须先找声母再找韵母，而不能先找韵母再找声母。
  

5.7 索引覆盖

• 当一个select语句使用了平凡索引且查询列表中的列刚好是创建平凡索引时的所有或部门列，这时就可以直接返回数据，而不用回表查询，这样的现象称为索引覆盖
  
• 通过索引查找的列，包含在索引中，不需要回表查询，这种情况就是索引覆盖。
  

---

END

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4