首页 > 其他分享 >索引数据结构底层（全）

索引数据结构底层（全）

时间：2022-12-21 11:31:45浏览次数：70  
标签：聚集 Tree 节点 索引 数据结构 数据 主键 底层


读者忠告

由于本文内容篇幅较长，涵盖了大家学习上、工作上的绝大多数索引，建议大家每一小节都认真阅读并理解透彻，如有疑问可在评论区留言探讨；

文章目录

  • ​​读者忠告​​
  • ​​一、索引概述​​
  • ​​二、索引的数据结构​​
  • ​​2.1 B+Tree数据结构​​
  • ​​2.1.1 二叉树​​
  • ​​2.1.2 平衡二叉树​​
  • ​​2.1.3 B-Tree​​
  • ​​2.1.3.1 B-Tree的演变过程​​
  • ​​2.1.3.2 B-Tree的底层存储结构​​
  • ​​2.1.4 B+Tree​​
  • ​​2.1.5 InnoDB数据页​​
  • ​​2.1.5.1 操作系统的局部性原理​​
  • ​​2.1.5.2 InnoDB数据页管理​​
  • ​​2.2 Hash索引​​
  • ​​2.3 R-Tree索引​​
  • ​​2.4 全文索引​​
  • ​​三、聚集索引与非聚集索引​​
  • ​​3.1 概念​​
  • ​​3.2 聚集索引与非聚集索引底层原理图​​
  • ​​3.3 索引组织表​​
  • ​​3.4 聚集索引说明​​
  • ​​3.5 MyISAM引擎为什么只能创建非聚集索引？​​
  • ​​3.5.1 MySIAM引擎索引底层实现原理图​​
  • ​​3.6 InnoDB表能不能没有聚集索引？​​
  • ​​3.6 一级索引和二级索引​​
  • ​​四、其他索引​​
  • ​​4.4 覆盖索引​​
  • ​​4.4.1 覆盖索引概念​​
  • ​​4.4.2 覆盖索引应用​​
  • ​​4.4.3 覆盖索引总结​​
  • ​​4.2 前缀索引​​
  • ​​4.2.1 前缀索引概念​​
  • ​​4.2.2 前缀索引的应用​​
  • ​​4.2.3 如果建立的前缀索引有重复数据会怎么样？​​
  • ​​4.3 辅助索引​​
  • ​​五、 索引的类型​​
  • ​​六、总结​​
  • ​​好了，本篇就说到这里了，看完觉得有帮助的童鞋记得点赞！点赞！点赞！（重要的事情说三遍！）​​

一、索引概述

索引是帮助数据库快速查询数据的一种数据结构，在数据库中，数据库系统除了存储数据之外还维护着一种特殊的数据结构，这种数据结构以某种方式指向数据，这样就可以在这种数据结构上实现高级算法来查询数据，这种数据结构就是索引。

索引是啥？索引就是帮助我们快速查找数据的一种数据结构！没毛病！

  • 索引示意图：

我们来直观的感受一下，有建立索引和没有建立索引的直观感觉

索引数据结构底层（全）_mysql


如图所示，索引能够帮我们快速的定位到数据的具体位置，高效查询。一般来说，索引本身也很大，不可能全部存储在内存当中，因此索引往往以索引文件的形式存储在磁盘上。索引是用来提供高性能数据库的常用工具。

二、索引的数据结构

  • ​​B-Tree​​：常见的索引类型，B+Tree就是在此数据结构上做的优化
  • ​​Hash​​：是基于哈希表实现的，只有精确匹配索引所有列的查询才会生效。对于每一行数据，存储引擎都会对所有的索引列计算一个hash code,并将有的hash code存储在索引中，同时在哈希表中保存指向每个数据行的指针。
  • ​​R-Tree​​：R-Tree是B-tree在高维空间的扩展，也叫空间索引，主要用于地理空间数据类型，存储高维数据的平衡树。
  • ​​Full-text​​：Full-text索引就是我们常说的全文索引，它的存储结构也是B-Tree。主要是为了解决当须要用like查询时的低效问题。

索引是在MySQL的存储引擎层中实现的，而不是在服务器层实现的。所以每种存储引擎的索引都不一定完全相同，也不是所有的存储引擎都支持所有的索引类型的。

MyISAM、InnoDB、Memory三种存储引擎对各种索引类型的支持：

索引

InnoDB

MyISAM

Memory

B-Tree

支持

支持

支持

Hash

不支持

不支持

支持

R-Tree

不支持

支持

不支持

Full-text

5.6版本之后支持

支持

不支持

2.1 B+Tree数据结构

B+Tree是从最早的平衡二叉树演化而来的。在讲B+Tree之前必须先了解二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），B+Tree即由这些树逐步优化而来。

关于数据结构的演变，大家可以来到这个网站：​​Data Structure Visualization​​

索引数据结构底层（全）_mysql_02

2.1.1 二叉树

  • 特点：左子树的键值小于右子树的键值

我们按照顺序依次插入：​​4 2 6 1 3 5 7​​，得出如下二叉树：

索引数据结构底层（全）_数据结构_03


对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3+3) / 7 = 2.428次

二叉查找树是可以任意地构造的，谁规定我必须按照​​4 2 6 1 3 5 7​​​的顺序插入呢？同样是​​1,2,3,5,6,7​​​这六个数字，我的插入顺序为：​​1,2,3,4,6,5,7​​，得到如下二叉树：

索引数据结构底层（全）_索引_04

计算这颗树的平均查找次数：(1+2+3+4+5+6+6)/7=3.857次

这棵二叉树的查询效率明显就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称AVL树。

2.1.2 平衡二叉树

平衡二叉树（AVL树）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度最大差为1。

我们按顺序插入​​6,3,7,2,4,1,5​​等数据，观察AVL树与普通二叉树：

索引数据结构底层（全）_数据库_05

平衡二叉树对于二叉树来说相对较为规则，有效的减少了数据的检索次数，提高了查询效率。

2.1.3 B-Tree

B-Tree又叫多路平衡搜索树，一颗m叉的B-Tree特性如下：

  • 树中每个节点最多包含m个孩子（m是叉数，2叉最多包含2个节点，3叉最多包含3个节点）。
  • 除根节点与叶子节点外（非根叶子节点），每个节点至少有[ceil(m/2)]个孩子。
  • 若根节点不是叶子节点（说明树的层级最少为2），则至少有两个孩子。
  • 所有的叶子节点都在同一层。
  • 每个非叶子节点由n个key与n+1个指针组成，其中[ceil(m/2)-1] <= n <= m-1
2.1.3.1 B-Tree的演变过程

我们以5叉B-Tree为例，根据公式推导[ceil(m/2)-1] <= n <= m-1，所以 2 <= n <=4 。当n>4时，中间节点分裂到父节点，两边节点分裂

我们依次插入：​​68 78 71 65 72 69 75 81 77 70 87 76 84 90 68 80 82 88 89 83​​等数字，观察B-Tree的演变过程

1）我们插入​​68,78,71,65​​，查看B-Tree的构成：

索引数据结构底层（全）_sql_06

2）插入​​72​​​，n>4，中间元素​​71​​向上分裂到新的节点

索引数据结构底层（全）_数据结构_07

3）插入​​69,75,81​​不需要分裂

索引数据结构底层（全）_索引_08

4）插入​​77​​​，中间元素​​77​​​向上分裂到父节点​​71​​

索引数据结构底层（全）_数据结构_09

5）插入​​70,87,76,84​​不需要分裂

索引数据结构底层（全）_数据结构_10

6）插入​​90​​​，中间元素​​84​​向上分裂到父节点中

索引数据结构底层（全）_mysql_11


7）插入​​68​​​，中间元素​​68​​向上分裂到父节点中

索引数据结构底层（全）_mysql_12

8）插入​​80,82,88,89​​不需要分裂

索引数据结构底层（全）_数据结构_13


9）最后插入​​83​​​，​​78,80,81,82​​​节点n>5，中间节点​​81​​​向上分裂，但分裂后父节点​​68,71,77,84​​​的n>5，中间节点​​77​​向上分裂

索引数据结构底层（全）_sql_14

2.1.3.2 B-Tree的底层存储结构

刚刚我们了解了一个B-Tree的完整演变过程，Data Structure Visualization这个网站并没有很好的显示B-Tree底层的一个结构情况（忽略了很多细节），例如没有显示指针、数据块、磁盘块等，我们手动画一张完整的B-Tree结构图：

我们按照顺序插入如下数据：​​26 18 2 11 19 29 80 37 6 42 15 21 30 44 43 53 5 36 28 29 33 60 58 75​​

得到如下B-Tree结构：

索引数据结构底层（全）_索引_15


我们把B-Tree补充完整（指针、数据块、磁盘块等）：

索引数据结构底层（全）_索引_16

每个节点都会占用一个磁盘块的磁盘空间，当在数据检索时，会将此磁盘块加载到内存中，每个非根节点上都有两个升序排序的键值和三个指向子树的指针，该指针存储的是子节点所在磁盘块的内存地址

以磁盘块1为例，假设现在加载了磁盘块1到内存中，我们通过磁盘块的三个指针（P1、P2、P3）就能够判断，P1指针指向的子树的数据范围为小于26，P2指针指向的子树的数据范围为26~37，P3指针指向的子树的数据范围为大于35。

  • 模拟查找关键字21的过程：

1）首先加载根节点，根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】

2）发现21比26小，根据磁盘块1中的P1指针找到对应的磁盘2，读入内存。【磁盘I/O操作第2次】

3）发现21比18大，根据磁盘块2中的P3指针找到磁盘块7，读入内存。【磁盘I/O操作第3次】

4）根据磁盘块7中的数据找到21。

观察查找过程：

索引数据结构底层（全）_数据库_17

  • 再模拟查找关键字28的过程：

1）首先加载根节点，根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】

2）发现28比26大且比37小，根据磁盘块1中的P2指针找到对应的磁盘3，读入内存。【磁盘I/O操作第2次】

3）发现28比19小，根据磁盘块3中的P1指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】

4）根据磁盘块8中的数据找到28。

观察查找过程：

索引数据结构底层（全）_数据结构_18

2.1.4 B+Tree

B+Tree在原B-Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，提高区间访问的性能。并且B+Tree数据结构将数据全部存储在最底层的叶子节点，这样可以保证每个磁盘块能够存储更多的指针，在一次IO磁盘开销中，查询到的数据更多。

我们按照如下顺序插入数据：​​26 18 2 11 19 29 80 37 6 42 20 28​​；

得到如下B+Tree结构：

索引数据结构底层（全）_数据库_19

我们仔细观察B+Tree会发现，所有的数据都保存了一份到最底层的叶子节点上，其他的叶子节点上只是保存行数据的主键值

索引数据结构底层（全）_sql_20


我们把B+Tree补充完整（指针、数据块、磁盘块等）：

索引数据结构底层（全）_数据库_21

在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。这样提高了磁盘块之间的区间访问性能

2.1.5 InnoDB数据页

2.1.5.1 操作系统的局部性原理

我们知道数据最终是存储在磁盘上，当我们要做数据处理时，需要把磁盘中的数据调出到内存中来进行处理，这个过程会产生磁盘的IO（输入输出），由于磁盘IO是非常昂贵的操作，所以计算机操作系统对此做了优化。每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中

当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。一页的大小与操作系统有关，一般为4k或者8k。这也就意味着读取一页内数据的时候，实际上发生了一次磁盘IO。

2.1.5.2 InnoDB数据页管理

在InnoDB中，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数​​innodb_page_size​​将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：

show variables like 'innodb_page_size';

而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

  • B-Tree：

B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

  • B+Tree：

在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为​​10^3​​ ）。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。

2.2 Hash索引

索引数据结构底层（全）_数据结构_22

2.3 R-Tree索引

索引数据结构底层（全）_索引_23

2.4 全文索引

索引数据结构底层（全）_数据库_24

关于Hash索引、R-Tree索引、全文索引的内容牵扯范围太广，因此打算后期出专门的专题来讲解；本章就不讲解了；

三、聚集索引与非聚集索引

3.1 概念

​​聚集索引​​：也叫聚簇索引（ClusterIndex），一般来说是以主键创建的索引，一张表只能有一个聚集索引，而且只有InnoDB能够创建聚集索引。

​​非聚集索引​​：也叫普通索引、辅助索引（Secondary Index），除了聚集索引外的索引都是非聚集索引。

聚集索引的数据存放在B+Tree索引树的叶子节点上，而非聚集索引的B+Tree索引树上只会存储当前索引列的数据与主键索引列的数据，并不会存放整行数据，当需要通过非聚集索引去检索一行数据时，首先非聚集索引通过索引树找到主键，然后通过主键去主键建立的B+Tree上查询出整行的数据；

上面这句话很重要，务必记牢！

3.2 聚集索引与非聚集索引底层原理图

我们通过聚集索引与非聚集索引的底层原理图来直观的感受下两者的区别

  • 聚集索引与非聚集索引示意图：

索引数据结构底层（全）_sql_25

在这里提一下，回表查询需要把聚集索引加载进内存，首先加载的应该是根节点，而不是直接定位到叶子节点，这里方便画图就没有画出来；

通过上面的索引图我们能够很直观的发现，普通索引（非聚集索引）的查询如果查询到了其他列的数据，那么需要借助主键索引来查询整行的数据，这个过程也称为回表查询；

3.3 索引组织表

其实，MySQL中的表的所有的数据都是按照主键排序的方式存储在一颗B+Tree上（InnoDB引擎），这颗B+Tree也叫聚集索引，所以叫MySQL叫索引组织表；

索引组织表的数据按主键排序手段被存储在B+Tree索引中，除了存储主键列值外还存储非主键列的值。普通索引只存储索引列，索引组织表就是索引（主键索引）存储表的所有列的值

3.4 聚集索引说明

关于聚集索引还有一个定义：数据行的物理排列顺序与该列值（主键）的逻辑顺序相同，并且一个表中只能拥有一个聚集索引。

什么是"数据行的物理排列顺序"？

数据行的物理排列顺序就是我们眼睛直观看到的列的排列顺序

索引数据结构底层（全）_数据库_26

一般来说我们主键都是自增的，大小都是从小到大，因此会忽略一个问题：数据行的物理排列顺序与聚集索引的排列顺序是保持一致的，

我们把"小军"的ID改为50，重新查看数据库表，发现排列顺序如下：

索引数据结构底层（全）_索引_27

发现数据行的物理排列顺序默认是和主键顺序保存一致的；

在InnoDB中，数据表中的物理排列顺序始终会保持与聚集索引的逻辑顺序一致；而聚集索引底层是一个B+Tree索引树，自然而然逻辑排列顺序是：从小到大顺序排列；因此数据表中的物理排列顺序是根据主键来排序的，也就是我们刚刚说的聚集索引的逻辑顺序；

这也是网上很多人说聚集索引在一张表中只能有一个的原因，为什么呢？因为我数据表的逻辑排列顺序要与聚集索引的排列顺序保持一致呀！那如果有多个聚集索引我到底跟谁保持一致呢？？

而且我们知道MySQL是索引组织表的，如果聚集索引有多份，那么数据是否也会存在多份呢？这样存储效率明显下降

3.5 MyISAM引擎为什么只能创建非聚集索引？

我们都知道InnoDB是底层存储文件是分为：​​.frm​​​（表空间文件）、​​.idb​​（索引文件和数据文件）；

MyISAM则是分了三个文件：​​.frm​​​（表空间）、​​.MYD​​​（数据文件）、​​MYI​​（索引文件）；

3.5.1 MySIAM引擎索引底层实现原理图

虽然MyISAM和InnoDB的索引底层采用的都是B+Tree数据结构，但MyISAM和InnoDB索引的底层实现稍有不同：

索引数据结构底层（全）_数据结构_28

MyISAM没有聚集索引，MyISAM建立的都是普通索引（即使是主键）；

MyISAM引擎是没有聚集索引的，因为MyISAM引擎不属于索引组织表，即有单独的空间存储表数据，表数据并不是和主键建立的B+Tree存储在一起的；MyISAM表通过任何索引来查询数据都需要回表查询；

大家可以按照我3.4小节的方式修改一下id，看myisam引擎的表是否会根据主键进行排序（答案是不会的）

3.6 InnoDB表能不能没有聚集索引？

我们知道InnoDB表是属于索引组织表，整表的数据都需要根据主键（聚集索引）来排序，并且数据也是存储在主键（聚集索引）的B+Tree上的；那么万一我们在表中没有创建主键（聚集索引）那么怎么办呢？？？

InnoDB必须要有且只有一个主键（聚集索引）！！！不能没有主键（聚集索引）！！！

那奇了怪了，我在InnoDB建表的时候明明可以不创建主键（聚集索引）呀,也没见他报错呀，咋回事？？？？

是这样的，主键（聚集索引）对于InnoDB实在是太重要了，InnoDB不能没有他，如果你不创建他会根据规则来选出较为合适的一列来做聚集索引，实在不行他就帮你创建一个隐藏的列作为聚集索引，规则如下：

（1）如果表定义了主键，则该列就是聚集索引；

（2）如果表没有定义主键，则第一个​​not null unique​​列是聚集索引；

（3）以上条件都不满足：InnoDB会创建一个隐藏的​​row-id​​作为聚集索引；

现在知道聚集索引对InnoDB来说有多重要了吧？？？

3.6 一级索引和二级索引

大家多多少少有听过一些DBA大佬口中经常说一级索引、二级索引吧？啥是一级索引和二级索引？？？

关于一级索引的定义：索引和数据存储是在一起的，都存储在同一个B+Tree中的叶子节点。一般主键索引都是一级索引。

关于二级索引的定义：二级索引树的叶子节点存储的是本列索引值和主键值；而不是数据。在使用二级索引检索数据时，需要借助一级索引；也就是说，在找到索引后，得到对应的主键，再回到一级索引中找主键对应的数据记录。

咋一看怎么和聚集索引和非聚集索引那么像？？？

对！一级索引就是聚集索引；二级索引就是非聚集索引！！

四、其他索引

4.4 覆盖索引

4.4.1 覆盖索引概念

覆盖索引只是一个概念，MySQL官方并没有说明什么是覆盖索引，只为了表达一下"该SQL语句是使用索引覆盖查询的"，仅此而已；

覆盖索引（或称索引覆盖）：即从二级索引中就可以得到要查询的记录，而不需要查询聚簇索引中的记录（回表查询），很显然，聚簇索引就是一种覆盖索引，因为聚簇索引中包含了数据行的全部数据，而非聚集索引的话，要看SQL语句查询的列是在索引树上，如果不在则需要回表查询；简单的说就是查询的列要被所使用的索引覆盖，换句话说就是查询的列要在索引树上，不需要回表查询。

4.4.2 覆盖索引应用

使用覆盖索引的SQL语句：只需要在一棵索引树上就能获取SQL所需的所有列数据，无需回表，速度更快。

我们给username列加上索引：

create index idx_name on t_user(username);
  • 执行如下SQL：
-- username创建的B+Tree上有值（使用了覆盖索引）
explain select username from t_user where username='xxx';

-- username创建的B+Tree上有值（使用了覆盖索引）
explain select id,username from t_user where username='xxx';

-- username创建的B+Tree上没有值,age列需要回表到聚集索引上去查询（没有使用覆盖索引）
explain select id,username,age from t_user where username='xxx';

索引数据结构底层（全）_数据库_29

上面提一下，有得时候MySQL的执行计划不是非常准确，因为MySQL底层有优化器来优化SQL，所以我们看到的执行计划的信息有得时候可能不是很准确

4.4.3 覆盖索引总结

覆盖索引：查询的数据被索引树覆盖了，即：查询的数据在索引树上，不需要回表查询；

4.2 前缀索引

4.2.1 前缀索引概念

前缀索引也是一种概念，或者说是操作索引的一种技巧；当索引列的数据是非常大时，那么该列建立的索引会非常大，而且检索速度也会很慢，这个时候我们考虑能否让该列的前面几个字符拿出来建立索引，而不是整列是数据建立索引，因此前缀索引的概念就由此产生；

我们知道前缀索引其实就是拿出该列数据的前几个字符出来建立索引来降低索引的大小，以及加快索引的速度的一种技巧性索引，但是毕竟前面几个字符不能够代替整列数据，有可能重复，我们应该尽量的减低重复的概率，提高不重复的概率，这样的前缀索引检索速度更快；

4.2.2 前缀索引的应用

  • 数据准备：
CREATE TABLE `student`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `name` varchar(20) DEFAULT NULL,
  `birthday` varchar(20) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB ;

-- ----------------------------
-- Records of student
-- ----------------------------
INSERT INTO `student` VALUES (1, '小明', '1999-10-20');
INSERT INTO `student` VALUES (2, '小军', '1999-02-21');
INSERT INTO `student` VALUES (3, '小龙', '1999-01-19');
INSERT INTO `student` VALUES (4, '小刚', '1999-06-06');
INSERT INTO `student` VALUES (5, '小红', '1999-02-05');
  • 计算不重复率：
mysql> select 1.0*count(distinct birthday)/count(*) from student;
+---------------------------------------+
| 1.0*count(distinct birthday)/count(*) |
+---------------------------------------+
|                               1.00000 |
+---------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,1))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,1))/count(*) |
+-----------------------------------------------+
|                                       0.20000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,2))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,2))/count(*) |
+-----------------------------------------------+
|                                       0.20000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,3))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,3))/count(*) |
+-----------------------------------------------+
|                                       0.20000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,4))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,4))/count(*) |
+-----------------------------------------------+
|                                       0.20000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,5))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,5))/count(*) |
+-----------------------------------------------+
|                                       0.20000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,6))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,6))/count(*) |
+-----------------------------------------------+
|                                       0.40000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,7))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,7))/count(*) |
+-----------------------------------------------+
|                                       0.80000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,8))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,8))/count(*) |
+-----------------------------------------------+
|                                       0.80000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

mysql> select 1.0*count(distinct left(birthday,9))/count(*) from student;
+-----------------------------------------------+
| 1.0*count(distinct left(birthday,9))/count(*) |
+-----------------------------------------------+
|                                       1.00000 |
+-----------------------------------------------+
1 row in set (0.00 sec)

发现不重复率在​​birthday​​字段在第9个字符时，达到100%，也就是说，在的倒数第二个字符时，数据没有重复的。

索引数据结构底层（全）_数据结构_30

计算出不重复率最高时是在该列的低9个字符，因此我们可以把第9个字符之外的数据不用建立索引，来降低索引的大小，提高索引的检索速度；

alter table student add key(birthday(9));

下次根据birthday字段查询，会发现使用了索引查询：

explain select birthday from student where birthday='1999-02-21';

索引数据结构底层（全）_数据结构_31

4.2.3 如果建立的前缀索引有重复数据会怎么样？

我们刚刚建立前缀索引时，首先要计算不重复率，然后再根据得出合适的位置来建立索引，那么如果不计算不重复率会怎么样？？

我们把刚刚建立的索引删除，在第4个字符位置上建立索引

alter table student drop index birthday;

alter table student add key(birthday(4));

索引数据结构底层（全）_索引_32

执行如下SQL分析执行计划：

explain select birthday from student where birthday='1999';

explain select birthday from student where birthday='1999-02-21';

explain select birthday from student where birthday='1999-10-21';

索引数据结构底层（全）_sql_33


我们随机执行了几条SQL语句，发现都没有走索引查询，而是全表顺序扫描，因为重复的数据太多了（占整表数据），MySQL优化器认为走索引还不如不走索引，因此选择顺序扫描查询；

我们切换个案例，把索引前缀字符切换为7：

alter table student drop index birthday;

alter table student add key(birthday(7));

索引数据结构底层（全）_数据结构_34


执行如下SQL：

explain select birthday from student where birthday='1999-10-21';

explain select birthday from student where birthday='1999';

索引数据结构底层（全）_数据库_35

4.3 辅助索引

辅助索引就是辅助我们查询的所有，一般指的就是非聚集索引（二级索引）

辅助索引就是二级索引，so，就这么简单！！！！ 关于二级索引的概念不用再说了吧？？

五、 索引的类型

到这里我们差不多已经了解了学习上、工作上绝大多数索引了，包括什么B-Tree索引、B+Tree索引、R-Tree索引、Hash索引、全文索引、聚集索引、唯一索引、二级索引、一级索引、覆盖索引、前缀索引。

除此之外我们应该还有听说过复合索引、唯一索引、普通索引、主键索引、非唯一索引…

这么多索引我们该怎么记？？以及该如何区分？？

我们看待事物的角度不同，索引也可以分为以下角度：

  • 数据结构角度：
  • B+Tree索引
  • R-Tree索引（空间索引）
  • Hash索引
  • Full-text索引（全文索引）
  • 物理存储角度
  • 聚集索引 （一级索引）
  • 非聚集索引（二级索引）
  • 逻辑角度
  • 主键索引
  • 普通索引（单列索引）
  • 多列索引（复合索引）
  • 唯一索引
  • 非唯一索引
  • 空间索引
  • 业务角度
  • 覆盖索引
  • 前缀索引
  • 辅助索引（非聚集索引）

我们平常所说的索引，如果没有特别指明，都是指B+Tree结构组织的索引。其中聚集索引、复合索引、前缀索引、唯一索引默认都是使用 B+tree 索引，统称为索引。

六、总结

  • 树的演变：二叉树演变平衡二叉树（AVL树）、平衡二叉树演变多路平衡搜索树（B-Tree）、B-Tree演变B+Tree
  • B+Tree相对于B-Tree的改进：将数据都存放在叶子节点，让每一个磁盘块都能够存储更多的指针，减少IO检索次数，并且叶子节点都加上循环链表，提高区间访问能力
  • 操作系统的局部性原理：计算机操作系统每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中
  • InnoDB数据页管理：InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB，因此B+Tree数据结构可以使InnoDB每次读取一页时可以获取更多的指针，查询更多的数据
  • 聚集索引与非聚集索引：聚集索引的数据和指针是存储在一起的，非聚集索引的B+Tree上只存储索引列的值与主键值，当使用非聚集索引查询数据时，如查询的列包含其他列数据，则需要借助主键回表查询；
  • MyISAM引擎为什么不可以建立聚集索引？：MyISAM存储引擎有单独的空间存储表数据，表数据并不是和主键建立的B+Tree存储在一起的，在MyISAM引擎中任何的索引都需要回表查询，具体参考​​3.5.1​​小节的：MyISAM存储引擎B+Tree底层实现原理图
  • 索引组织表：MySQL中的表的所有的数据都是按照主键排序的方式存储在一颗B+Tree上（InnoDB引擎），所以MySQL也叫索引组织表；
  • InnoDB能不能没有主键？：InnoDB必须要有且只有一个主键（聚集索引），不能没有主键，具体为什么参考​​3.6​​小节
  • 什么是一级索引索引？什么是二级索引？：一级索引就是聚集索引，二级索引就是非聚集索引，MyISAM引擎不可建立一级索引，建立的都是二级索引
  • 索引覆盖：覆盖索引只是一个概念，即查询的数据列在二级索引上，不需要回表查询，此时就说查询的数据"被索引覆盖了"，也叫索引覆盖，或称覆盖索引。聚集索引就是一种覆盖索引，因为聚集索引上包含了整行的数据；
  • 前缀索引：前缀索引也是一种概念，或者说是操作索引的一种技巧，当索引列非常大时，我们可以采取索引列数据的前面几个字符来建立索引，此时建立的索引就称之为前缀索引，注意前缀索引需要计算不重复率；
  • 辅助索引：辅助索引，顾名思义就是辅助我们查询的所有，所有的二级索引都成为辅助索引；
  • 索引的分类：索引的类型有非常非常多，我们刚刚也举例了，但我们可以按照不同的角度去看待索引，把索引归类好，其实索引也不难记住；一般划分为：数据结构角度、物理存储角度、逻辑角度、业务角度等；

标签：聚集,Tree,节点,索引,数据结构,数据,主键,底层
From： https://blog.51cto.com/u_15919174/5959201

相关文章

  • 索引下推总结
    索引下推（indexconditionpushdown）简称ICP，在Mysql5.6的版本上推出，用于优化查询。在不使用ICP的情况下，在使用非主键索引（又叫普通索引或者二级索引）进行查询时，存储引擎......
  • 打开MCMC（马尔科夫蒙特卡洛）的黑盒子 - Pymc贝叶斯推理底层实现原理初探
    打开MCMC（马尔科夫蒙特卡洛）的黑盒子-Pymc贝叶斯推理底层实现原理初探我们在这篇文章里有尝试讨论三个重点。第一，讨论的MCMC。第二，学习MCMC的实......
  • 模板系列---数据结构
    P3378【模板】堆题目简述给定三个操作，求数列中最小的数，删除数列中最小的数，插入一个新的数思路板子题没什么好说，用stl自带的优先队列很好写，但手写的也要掌握。建议......
  • 面试了十几个高级前端，竟然连（扁平数据结构转Tree）都写不出来
    「本文已参与好文召集令活动，点击查看：后端、大前端双赛道投稿，2万元奖池等你挑战！」前言招聘季节一般都在金三银四，或者金九银十。最近在这五六月份，陆陆续续面试了十几个高级......
  • 数据结构第一节：栈
    序：在经历了Acwing的“从入门到入土”，终于于今天进入了代码源的学习（心疼我好几百报的课阿T_T）。据y总言——”STL是提高C++编写效率的一个利器。“因此，为了提高我们编写代码......
  • 我说MySQL联合索引遵循最左前缀匹配原则，面试官让我回去等通知
    携手创作，共同成长！这是我参与「掘金日新计划·8月更文挑战」的第6天，点击查看活动详情面试官：我看你的简历上写着精通MySQL，问你个简单的问题，MySQL联合索引有什么特性？心......
  • 数据结构-二叉树遍历非递归
    前序遍历voidpreorder(BTNODEBT){BTNODESTACK[100];inttop=-1;STACK[++top]=BT;BTNODEp=null;while(top!=-1){BTNO......
  • 数据结构（起泡排序）
    #include<stdio.h>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;intCOMPARE(SSELEMENTa[],intn){inti,j,p,flag;i=n......
  • 技术分享 | InnoDB 排序索引的构建
    作者：SatyaBodapati翻译：管长龙从MySQL5.7开始，开发人员改变了InnoDB构建二级索引的方式，采用自下而上的方法，而不是早期版本中自上而下的方法了。在这篇文章中，我们将通过......
  • 技术分享 | 为什么 SELECT 查询选择全表扫描，而不走索引？
    作者：Charizard爱可生服务团队成员，主要负责公司数据库运维产品问题诊断；努力在数据库和IT领域里摸爬滚打中。本文来源：原创投稿*爱可生开源社区出品，原创内容未经授权不得随意......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99