MySQLB+树

书名《MySQL是怎样运行的:从根儿上理解MySQL》。

这本书真的很好。如果你想学习,我建议你去😊看看。

[En]

This book is really good. I suggest you check out 😊 if you want to learn.

本文是基于我的认识上将InnoDB的结构进行的回想,查缺补漏。

InnoDB记录结构

InnoDB是以页来存储数据的,一个页的大小为16KB。

InnoDB行格式有COMPACT行格式和Redundant行格式,以及MySQL默认的Dynamic行格式。

COMPACT行格式

MySQLB+树
  1. 变长字段的长度,按列逆序存放,c3,c2,c1列存储。
  2. null字段是否为null,表示一些可以为null的字段,具体占用大小具体字段多少,每个可以为null的字段占一位。同样是按列逆序存放,高位用0填充。
    MySQLB+树
  3. delete_mask 表示删除位,如果删除置1。1位
  4. min_rec_mask 表示非叶子节点的最小值
  5. n_owned 表示每页中最小节点拥有user record数量
  6. heap_no 表示当前记录在堆中的数量
  7. record_type 表示当前记录的类型,可以为普通记录0,索引记录1
  8. next_record 表示下一个数据的指针
  9. 隐藏列的信息
  10. row_id 表示当这个表中没有主键时会自动添加一个row_id充当其区别。但是当表中存在主键就会被其替代,不会出现。
  11. transation_id 事务ID
  12. roll_pointer 回滚指针
  13. 列的值,定长的就会直接用一定长度占用,没有占用的用0填充。不定长的就会被指定长度,然后占用其长度的位置。

补充:但是当我们指定的表是不定长的字符集时,会导致一些定长的列也会被列入不定长的列中,但是它会占用最小的空间。比如utf8是1-3字节不定长,char(10)如果没有用超过10个字节的话,最终还是会占用最低10个字符,不够用0填充,原因会产生碎片。

ERROR 1118 (42000): Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have to change some columns to TEXT or BLOBs。

它还显示,行表列表的最大大小为65535字节。当我们声明整列时,所有列的空间大小(包括列的固定间隔(固定长度+不定长度)),每列根据长度为1个字节或2个字节,每列不能为空或可以为空(根据列的空间来确定其长度)。因此,当我们声明大小时,我们需要判断它的大小,如果它大于65535字节,我们需要调整列的属性的大小。

[En]

It also shows that the maximum size of a row table list is 65535 bytes. When we declare the entire column, the space size of all columns * (including column fixed space (fixed length + indefinite length), each column according to the length of 1 byte or 2 bytes, each column can not be empty or can be empty (according to the column space to determine its length) * . So when we declare the size, we need to judge its size, and if it is greater than 65535 bytes, we need to resize the properties of the column.

mysql> create table varchar_demo(
    ->  c varchar(65532)
    -> ) CHarset=ascii row_format=compact;
Query OK, 0 rows affected (0.04 sec)

mysql> create table varchar_demo_01(
    ->  c varchar(65533)
    -> ) CHarset=ascii row_format=compact;
ERROR 1118 (42000): Row size too large. The maximum row size for the used table type, not counting BLOBs, is 65535. This includes storage overhead, check the manual. You have to change some columns to TEXT or BLOBs

我们使用的是ASCII字符集只占一个字节,可以发现65532字节 + 判断空的1个字节 + 长度2个字节 刚好是65535字节,当我们试图多加一个字节时就会报错。

Dynamic行格式:

其实和compact行格式差不多,但是它会在数据溢出时全部以引用的方式来引用,而不像compact一样留有768字节在原页中,然后剩余的使用引用的方式。

我们插入一条数据就是形成这样一种记录结构,我们想要快速找到数据,我们要学习数据页。

[En]

We insert a piece of data is the formation of such a record structure, we want to quickly find the data, we have to learn the data page.

InnoDB数据页结构

MySQLB+树
  • File-Header :
  • 存储了校验和用来验证数据页进行更新的主要部分。首先呢更新操作会直接将其头部这个File-Header覆盖,然后进行覆盖操作后,如果中途断电,覆盖失败,没有进行覆盖到File-Tailer,此时进行验证,发现头和尾的值值不一样,就会判定为更新失败。
  • 下一页和上一页的引用。用来形成页之间的双向链表
  • 页的类型是索引页还是数据页。
    MySQLB+树
  • infimum+supremum。也是一种数据行的形式,是页中固有的两个行。
  • Page Directory 页目录,就是存储页中槽的地方。

首先,我们来介绍一下在数据页面上加速查询数据的方法。

[En]

First of all, let’s introduce the method of speeding up querying data on the data page.

  1. 数据插入后会和最小页和最大页形成一个单向链表,并且数据是按主键的大小插入位置的。(主键建议自增,不然会增加开销)
  2. 然后会进行分组,最小页单独一组,后续4-8行一组,当数据插入组数量变多会出现组分裂为两个组,每组的最后一个数据行作为槽的引用,槽中存储数据行的引用和主键的值。
  3. 槽中的每个键值就存储的是引用和主键值,然后我们就二分查找主键值即可。

通过这种方式,可以根据槽中存储的每组最大值快速找到我们的数据行。

[En]

In this way, our data rows can be quickly found according to the maximum value of each group stored in the slot.

添加一个知识点:就是B+树中删除数据行并不会将其从地址中去除,可能就是把引用释放一下,然后就只是将其删除标记标记一下,下次有数据加入的时候就会直接将其占用。

B+树索引

索引是对每一页进行重新编目。

[En]

Indexing is the re-cataloguing of each page.

将每页的最小的主键作为key和页的索引作为值。当请求key就可以用二分的方法获得这个主键可能所在的页。

因为一个数据页的索引可以作为一个数据行,对于多个数据页的索引,即多个数据,也可以分组成一个索引页,如果数据很多,可以是多级索引页。这一数字将呈指数级增长。

[En]

For the index of a data page can be used as a data row, for the index of multiple data pages, that is, multiple data, they can also be grouped and grouped into an index page, and if there is a lot of data, they can be multi-level index pages. the number will grow exponentially.

MySQLB+树

在表创建时,会为主键创建一个聚簇索引。也就是向上面的B+树一样,叶子节点存储的是数据页,非叶子节点存储的是索引页。

但是我们也可以 创建索引,对于列再创建一个B+树即创建二级索引。

MySQL就会再维护一个B+树,此时叶子节点的数据行就是索引指定的列和主键组成的(我们会在进行一次回文,即拿着主键去聚簇索引中找数据);

索引节点指定列和页索引,但当指定的列有多个重复值时,它将成为指定的列+主键+页索引,以防止混淆多个页索引值。

[En]

The index node specifies the column and page index, but when the specified column has multiple duplicate values, it becomes the specified column + primary key + page index to prevent multiple page index values from being confused.

MyISAM索引方案

即数据存放在文件中,然后全部都拿着数据的引用和主键拼在一起。即数据是数据,索引就是索引。不像B+树一样,叶子节点是存放数据行,这个存储引擎则是全部都是索引行,直接拿着地址文件中找数据。

Original: https://www.cnblogs.com/duizhangz/p/16282409.html
Author: 大队长11
Title: MySQLB+树

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/505373/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球