Notes
Search…
Storage
B 树B+ 树的索引结构我们已经介绍,但是它们是怎么在磁盘上存储的呢?
记录是按照行存储的,但是读取的时候并不是以行为单位。在数据库中,无论读多少行,都是将这些行所在的页加载。也就是说,数据库磁盘存储的基本单位是页(Page)。
如下图,一个表空间包含一个或多个段,一个段包含一个或多个区,一个区包含了多个页,一个页有多行记录。
表空间(Tablespace)是一个逻辑容器,与段是 1:n 的关系。数据库由一个或多个表空间组成,从管理上可分为系统表空间、用户表空间、撤销表空间、临时表空间。查看表空间类型:
1
# ON 表示每张表会单独保存为一个 .ibd 文件
2
show variables like 'innodb_file_per_table';
Copied!
(Segment)与区是 1:n 的关系,段不要求区与区之间是连续的。当我们创建数据表、索引的时候,会创建相应的段,比如表段、索引段。
(Extent)在 InnoDB 引擎中,一个区会分配 64 个连续的页,所以区的默认大小是 64 * 16KB = 1MB。
(Page)存储多行记录,在 InnoDB 中默认大小为 16KB。按照类型分的话,常见的有数据页(保存 B+树的节点)、系统页、Undo 页、事务数据页等。查看页的大小:
1
show variables like '%innodb_page_size%';
Copied!
数据页包含 7 个部分,如下图:
  • 文件通用部分:文件头(File Header)和文件尾(File Tailer),类似包装盒,将页的内容包装起来,通过文件头和文件尾检验的方式来确保页传输是完整的。
    • 文件头中有两个字段,FIL_PAGE_PREV 和 FIL_PAGE_NEXT,分别指向上一数据页和下一数据页,相当于双向链表。所以一个区中 64个页是逻辑上的连续,而不是物理上的。
    • 文件头给出 checksum ,到文件尾的时候整体运算出 checksum,两者一致才说明整个页传输是完整的。
  • 记录部分:最大最小记录(Infimum+supremum)、用户记录(User Records)、空闲空间(Free Space)占用了页结构的主要空间。当有新的记录插入时,会从空闲空间中进行分配存储。
  • 索引部分:指页目录(Page Directory),用户记录的目录,由于用户记录是顺序存储的,所以检索效率不高,有了页目录,就有二分查找的方式。如下图:
  1. 1.
    一个数据页中所有记录分成几组,不包括已删除记录。
  2. 2.
    第一组:最小记录,只包含一条;最后一组:包含最大记录,1-8条记录;其他组:4-8条记录。
  3. 3.
    每个组的最后一条记录中的头信息会存储该组有多少条记录,n_owned 字段。
  4. 4.
    页目录存储每组最后一条记录的地址偏移量,每组的地址偏移量叫做槽(slot),每个槽指向不同组的最后一条记录。
我们看看怎么进行二分查找,比如我们要查找主键为 9 的记录:
  1. 1.
    low = 0, high = 4, (0 + 4) / 2 = 2,2 对应的最大记录为 8。
  2. 2.
    9 > 8,所以 low = 2, high = 4, (2 + 4) / 2 = 3,3 对应的最大记录为 12。
  3. 3.
    9 < 12,所以在槽 3 中进行查找,遍历槽 3,找到 9。

B+ 树与页的关系

  • 在 B+ 树中,每个节点都是一个页。
  • 同一层上的节点通过数据页中文件头的两个指针形成一个双向链表。
  • 非叶子节点有多个索引行,每个索引行存储索引键和指向下一层页面的数据页指针。
  • 叶子节点,存储了关键字和行记录,在数据页内部的多条记录是一个单向链表。通过对页目录进行二分查找。
Last modified 2yr ago
Copy link
Contents