深入理解Mysql索引及其物理存储

数据库基础

• 最上层用于连接、线程处理；第二层中包含了大多数的核心服务，包括了对 SQL 的解析、分析、优化和缓存等功能，存储过程、触发器和视图都是在这里实现的；而第三层就是真正负责数据的存储和提取的存储引擎，例如：InnoDB、MyISAM等
  %% 其本质应该属于数据库的三级模式，存储引擎相对于内模式

数据存储结构

• 使用不同的存储引擎来存储数据，绝大多数存储引擎都以二进制的形式存储数据
• 在 InnoDB 存储引擎中，所有的数据都被逻辑地存放在表空间中，表空间tablespace是存储引擎中最高的存储逻辑单位，在表空间的下面又包括段segment、区extent、页page
• 同一个数据库实例的所有表空间都有相同的页大小；默认情况下，表空间中的页大小都为 16KB，当然也可以通过改变 innodb_page_size 选项对默认大小进行修改，需要注意的是不同的页大小最终也会导致区大小的不同
• ++一页有多行，一区有多页，一段有多区，一表空间有多段。++
• 而且页在区中的存储限制：在 InnoDB 存储引擎中，一个区的大小最小为 1MB，页的数量最少为 64 个，那么就相当于页的大小最多为16KB
• 数据插入时，数据库会分配新的数据页用于存放数据。MySQL一般都是一个extent为单位进行申请。我们在本地建个MySQL，然后慢慢往里面写数据，你会发现这个表的数据文件大小，是一段段增加的。++以区为申请单位，以页为数据分配存储单位++

随机读取和顺序读取

%% 在我们常用的sql理解中，数据是以行的形式读取出来的，其实不然，通过上述的结构，我们可以了解到，单次从磁盘读取单位是页，而不是行，也就是说，即便只读取一行记录，从磁盘中也是会读取一页的。单页读取代价较高，所以一般都会进行预读::理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用::

• 程序运行期间所需要的数据通常比较集中。磁盘顺序读取的效率很高不需要寻道时间，只需很少的旋转时间
• 对于具有局部性的程序来说，预读可以提高I/O效率，预读的长度一般为页page的整倍数

数据读取过程

• 关系型数据库管理系统最重要的一个目标就是，确保表或者索引中的数据是随时可以用的。那么为了尽可能的实现这个目标，会使用内存中的缓冲池来最小化磁盘活动::每一个缓冲池都足够大，大到可以存放许多页，可能是成千上万的页::

• 缓冲池管理器将尽力确保经常使用的数据被保存于池中，以避免一些不必要的磁盘读。如果一个索引或者表页在缓冲池中被找到，那么将会处理很快。

• ::如果在内存缓冲池中，没有找到数据，会从磁盘服务器的缓冲区里面去读取::磁盘服务器的缓冲区，如同数据库的缓冲池读取一样，磁盘服务器试图将频繁使用的数据保留在内存中，以降低高昂的磁盘读取成本。这个读取成本大概会在1ms左右

  • ++会不会二者有很多重复值？考虑一下DBMS的内存缓冲池和磁盘服务器的缓冲区会不会存在什么关系？++

• 如果磁盘服务器的缓冲池中依然没有找到数据，此时就必须要从磁盘读取了，此时读取又分为随机读取和顺序读取

随机I/O

%% 随机IO：读写操作时间连续，但访问地址不连续，随机分布在磁盘的地址空间中

• 一个页包含多条记录，我们可能需要该页上的所有行，也可能是其中一部分，但所花费的时间成本都是相同的。读取一个页，就有一次随机I/O, 大约需要10ms的时间，很久！::这个地方的前提应该是我们需要将多个页加载到内存中，但是页不连续::

顺序读取

• 预读和缓存等机制对顺序IO会有更好的效果。如果我们将多个页读取到缓冲池中，并按顺序处理它们，此时读取的速度变的很快
• 顺序读取快速且支持预读，且不需要寻道时间，只需要少量的旋转时间

索引

%% 索引是为了加速对表中数据行的检索而创建的一种分散存储的数据结构。距离明白又进了一步：数据的存储都是在表空间中，而索引只是用来加快检索的一种存储结构，里面存储一定量的数据，如果命中索引，则索引中的数据会被很快的返回，如果没命中，那么就会到表空间中取出目标数据。

• 一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级

  • 所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数

• 文件系统及数据库系统的设计者利用了磁盘预读原理，将一个节点的大小设为等于一个页(page)，每页大小4kb或8kb左右，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在B+Tree每次新建一个节点的同时，直接申请一个页的空间::应该是先申请extent区，再申请分配一个页::

  • 这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个节点node只需一次I/O

• 树的高度决定了I/O的次数，树高度越低，那么I/O性能就越好；

%% 也就是说，因为磁盘的操作费时费资源。那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？现在数据库存储的数据结构一般都是树，磁盘查找存取的次数往往由树的高度所决定，所以，我们需要一种高度较低的树结构

数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL树或者红黑树，我们每一个树结点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里。但如之前所说：从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的。::这是磁盘I/O的一大特点 ::根据这个思路,我们可以在一个树节点上尽可能多地存储数据,一次磁盘 IO 就多加载点数据到内存,这就是 B 树，B+树的的设计原理了。::使每一个结点的容量大小正好或者接近一个磁盘块(数据页，一般是16k)的大小::
树结构特性决定了遍历数据方式本身就纯天然的支持按区间查询

B树

B树

• 17、35是第一层的关键字节点，有P1、P2、P3三路，小于走左边查找，大于走右边查找，位置之间的走中间查找；

• 一般来说路的数=关键字数+1::如图中两个关键字最多可以有三条路径::

  • 每个节点存储的关键字是有一定的总容量的，所以索引的字段名影响着存储关键字的字数
  • 如果索引关键字节点（每个节点能存储4kb数据）的索引字段名称越短，每个节点存储的关键字数越多，路数也会变多，那么就导致了树的层级变低，每次I/O能够查找到数据的机会就越大，这样整体上就减少了I/O的搜寻次数，提高了效率

• B树的特点

  • 不再是二叉搜索，而是m叉搜索，高度相比二叉树能够大大降低
  • 叶子节点，非叶子节点，都存储数据，每个节点可以存储j个记录，如果将节点大小设置为页大小，例如4K，能够充分的利用预读的特性，极大减少磁盘IO::节点可以视为页的存储，可以是页的任意倍数，但是如果和页的大小相同，那么预读就可以按节点预读，很方便，很高效::
  • B树如果要求遍历，则最好为中序遍历，可以获得所有节点
    • 因为由于B树的特性，中序遍历会按照键值的递增顺序访问所有的键值。
  • 但是兄弟节点之间只有数据，缺少指针，所以中序遍历的效率并不高。

B+树

特点

• 非叶子节点不再存储数据，数据只存储在同一层的叶子节点上；
• 叶子之间，增加了指针，使叶子节点构成了链表。获取所有节点，不再需要中序遍历

这些改进让B+树比B树有更优的特性：

• 范围查找，定位min与max之后，中间叶子节点就是结果集，不用中序回溯；范围查询在SQL中用得很多，这是B+树比B树最大的优势

  • 在B树中，兄弟节点之间没有直接的链接，而在B+树中，所有的叶子节点都通过指针相互连接，形成一个有序链表。这样，对于需要对一定范围内的数据进行操作的查询，B+树比B树有更高的效率。比如说，如果你想要获取所有键值在[10, 20]这个区间内的数据，使用B+树，你只需要找到第一个大于等于10的键，然后沿着叶子节点的链表顺序遍历即可，而使用B树，你可能需要遍历树中的多个分支。
  • 这也是为什么在很多数据库系统和文件系统中，B+树更为常用。因为在这些系统中，经常需要处理范围查询这类操作，B+树的设计能更好地满足这类需求。
  • 和Clickhouse简直是异曲同工！CK其实就是增加了PK的专业性，但是定位min和max还是和mysql极其类似！

• 跳表：支持二分查找的有序链表(动态数据结构)，其最大特点就是支持添加索引层，能够支持区间查询，每增加一层索引，查询效率就会提高。其查找、插入、删除的时间复杂度都是*O(logn)*级别

• B+树有点像前面的跳表，数据底层是数据，上层都是按底层区间构成的索引层，只不过它不像跳表是纵向扩展，不断增加索引的深度，而是横向扩展索引的“跳表”，只增加索引的个数，横向排列的宽度增加了。这么做的好处即减少磁盘的IO操作又提高了范围查找的效率。

  • 跳表是不断在数据层之上的索引层又建立索引层，一步一步提高查找效率，但是层数会越来越多，I/O磁盘操作也不可避免地升高
  • 而B+树在建立好索引层和指针层之后，插入数据都是横向扩展叶子节点宽度，保证层数还是矮矮的
  • 在B+树中，当插入数据的时候，索引结构也是在横向扩展。B+树的一项重要特性就是它的节点可以容纳多个元素。因此，当你插入数据的时候，如果当前的叶子节点还有足够的空间，新的数据就会被插入到这个节点中，这就是你所说的横向扩展。
  • 然而，如果当前的叶子节点已经满了，那么就会发生一个叫做分裂的操作。在分裂的过程中，当前的节点会被分成两个新的节点，并且一个新的索引键会被添加到它们的父节点中++这其实就是一种纵向扩展！++。这样，B+树就能保持它的平衡特性，也就是所有的叶子节点都处于同一层。因此，虽然在插入数据的过程中B+树可能会进行纵向的扩展，但是这种扩展是有限的，并且B+树的高度通常都保持在很低的水平，这就使得B+树的查找效率非常高。

• redis的有序集合zset数据结构底层采用了跳表原理

  • 使用跳表不用B+树的原因是：redis是内存数据库，而B+树纯粹是为了mysql这种IO数据库准备的。B+树的每个节点都是一个mysql分区页(阿里面试)

自平衡性：

• 自平衡性是指在进行插入和删除操作时，数据结构能够自动调整其内部的布局，保证所有的查询操作在最坏的情况下都有对数级别的时间复杂度。自平衡性是许多高级数据结构（例如B+树、跳表、AVL树、红黑树等）的重要特性，它能够保证数据结构在任何情况下都能提供良好的查询效率。

何时使用跳表，何时使用B+树：
跳表和B+树都是优秀的索引数据结构，选择哪种取决于你的特定需求和环境。以下是一些可能会影响你选择的因素：

1. 数据大小和内存限制：如果你的数据集相对较小，能够完全存储在内存中，那么跳表可能是一个不错的选择，因为它的实现比B+树简单且插入、删除、查找操作都非常高效。但如果你的数据集很大，需要在磁盘上存储，那么B+树可能是更好的选择，因为B+树是为磁盘存储和I/O操作优化设计的。
2. 并发控制：在多线程环境下，跳表通常更容易进行并发控制。因为跳表的插入和删除操作只需要修改少数节点的指针，所以更容易实现更细粒度的锁，这样可以降低锁冲突的可能性，提高并发性能。
3. 查询类型：如果你的应用主要进行范围查询（例如，查找所有的值在某个范围内的数据），那么B+树可能是更好的选择，因为B+树的叶子节点之间有指针连接，可以很方便地进行范围查询。而跳表虽然也能进行范围查询，但效率通常较低。
4. 实现复杂性：跳表的实现通常更为简单和直接。如果你需要自己实现这些数据结构，那么跳表可能是更好的选择。
5. 频繁的插入和删除操作：如果你的应用需要频繁地插入和删除数据，那么跳表可能会有更好的性能，因为它的插入和删除操作只需要修改少数节点的指针。
   总的来说，你需要根据你的特定需求和环境来选择最适合的数据结构。跳表和B+树各有优缺点，你需要根据自己的实际情况来进行选择。

关于两树叶子节点和非叶子节点的理解

• 叶子节点存储实际记录行，记录行相对比较紧密的存储，适合大数据量磁盘存储；非叶子节点存储记录的PK，用于查询加速，适合内存存储；++这个适合不太懂，索引文件不就是存在磁盘上吗？++
• 非叶子节点，不存储实际记录，只存储关键字(KEY)和下一层的索引，那么在相同内存的情况下，B+树能够存储更多索引::B树的节点不仅存储键值，还要存储数据::
  • 因此当我们需要有序遍历B+树所有关键字时，直接从最小关键字的叶子结点开始遍历即可。通过头结点往下找到第一个叶子结点，然后在叶子结点的链表上就行遍历即可完成区间查询。
  • B+树的非叶子结点不存储Data域，因此它可以存储更多个关键字和下一层结点的指针::忘了Mongodb里的B树长啥样了吗？节点既要有关键字，也要存放数据。::而B+树中非叶子节点全部存储关键字和指针，就会划分更细更多的数据范围，减少了一层树再一层树的范围划分，因此相同的数据量下B+树会比B树更矮胖
  • 因为B+树比B树更矮，所以B+树所进行的I/O次数更少。因为途中经过每一层，我们都需要进行一次I/O读取一个结点，B+树会更矮，途径的层数会更少，进而I/O次数也会更少

聚集(主键)索引和非聚集(二级)索引

• 聚集索引：数据行存储的物理顺序与聚集索引值的逻辑顺序相同(查询效率快的原因)，数据的物理存储顺序其实就是默认以主键值的大小为顺序进行存储的(数据页的记录存储方式)

  • 如数据表中已经插入主键值为1、3、5、7、9的数据(存储顺序以主键值大小顺序进行存储)，此时我要插入主键值为4的数据记录，此时磁盘上数据的存储顺序就变成了1、3、4、5、7、9
  • 这也是聚集索引修改慢的原因，插入数据可能造成数据的移动，而数据的移动可能会影响数据的物理存储顺序，需要对数据页进行重排序，开销很大，所以一般采取主键自增
    • 但是聚集索引查询快！
  • Innodb采用聚集索引，数据与索引聚集，Data域存的是数据本身。索引也是数据::?索引是数据结构啊？::数据和索引存在一个XX.IDB文件中，所以也叫聚集索引

• 聚集索引可以创建在任何一列你想创建的字段上，这是从理论上讲，实际情况并不能随便指定，否则在性能上会是恶梦

  • InnoDB必须至少有一个聚集索引，但可以没有主键
  • 如果未使用 UNIQUE 属性创建聚集索引，数据库引擎将向表自动添加一个四字节 uniqueifier 列。必要时，数据库引擎将向行自动添加一个 uniqueifier 值，使每个键唯一且非空。此列和列值供内部使用，用户不能查看或访问

• 如果想查询学分在60-90之间的学生的学分以及姓名，在学分上创建聚集索引是否是最优的呢？

  • 答：否。既然只输出两列，我们可以在学分以及学生姓名上创建联合非聚集索引，此时的索引就形成了覆盖索引，即索引所存储的内容就是最终输出的数据，这种索引在比以学分为聚集索引做查询性能更好

MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，如果在where中出现对索引的判断语句，那么就对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。先过滤不满足条件的记录，再去进行回表。当然，如果判断语句较少，其带来的性能提升就会小很多

%% 在理解回表这个概念之前，我们需要了解一下关于数据库索引的一些基本知识。在关系型数据库中，索引是一种用来快速查找数据的数据结构。一个表可以有多个索引，每个索引都是针对表中的一个或多个字段建立的。索引中保存的并不是完整的行数据，而只是索引字段的值和一个指针，这个指针指向存放完整行数据的地方(页指针，不是磁盘物理位置) %%

%% 当我们根据某个条件进行查询时，数据库会先去对应的索引中查找，找出满足条件的索引项，然后根据索引项中的指针，回到表中取出完整的行数据这个从索引到表的过程就叫做回表在这个过程中，可能会涉及到磁盘I/O，因为表的数据可能并没有完全放在内存中，而需要去磁盘上读取，这是一个相对比较慢的操作。 %%

%% 通常来说，一次查询可能会涉及多次回表。比如说，你想查找年龄在20到30岁之间的所有人的信息，数据库会在年龄这个索引中找到所有满足条件的索引项，每找到一个，就需要回表一次取出完整的行数据。 %%

如果索引包含了查询所需要的所有字段，这种索引被称为覆盖索引，使用这种索引进行查询就不需要回表，因为所有需要的数据都可以直接从索引中获取。但是覆盖索引并不是在所有情况下都能使用，因为它需要索引包含所有的查询字段，这可能会导致索引变得非常大，占用大量的存储空间，同时也会降低写操作的性能。因此，在设计索引时，需要根据具体的查询需求和性能要求进行权衡。

• 非聚集索引：以非聚集索引值建立一颗新的B+树，比如主键为C1，我们经常以字段C2为条件进行查找，那可以在C2上建立一个非聚集索引，以C2值为关键字建立一棵B+树。当以C2为条件进行查找时，就以C2值在该B+树上进查找，查找到后，若需要select的字段存在叶结点中，则返回该值(称其为索引覆盖)，若不在，则需要进行回表操作
  • 由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段
  • 回表：主键索引的叶子节点存放的是整行数据，非主键索引的叶子节点存放的是主键的值和对应字段的数据
    • 也就是说，非聚集索引一定能查找到主键值？yes，答案在上
  • 非聚集索引的叶子层并不和实际数据页相重叠，采用叶子层包含一个指向表中的记录在数据页中的指针方式。非聚集索引层次多，不会造成数据重排序
  • 索引是索引，数据是数据。索引放在XX.MYI文件中，数据放在XX.MYD文件中，所以也叫非聚集索引
• 聚集索引的叶节点就是最终的数据节点，而非聚集索引的叶节仍然是索引节点，但它有一个指向最终数据的指针