Notes
  • Introduce
  • Go
    • Grammar
      • Basic
      • Goroutines & Channels
      • Test
    • System Library
      • Module
      • sync
      • context
      • net
    • Concurrency in Go
    • The Go Memory Model
    • Code Snippet
  • Rust
    • The Rust Programming Language
    • Rust by Example
  • JAVA
    • Preface
    • Grammar
      • Basic
      • Data Types
      • Operator
      • Exceptions
    • Class Libraries
      • Collection
      • Stream
      • IO
      • NIO
      • RMI
    • Concurrency
      • Preface
      • JMM
      • Synchronized & CAS
      • Deadlock
      • Thread
      • Lock & Condition
      • Utility Class
      • Thread-safe Collection
      • Atomic Class
      • Fork/Join
      • Concurrency Design Patterns
        • Immutable
        • Copy-on-Write
        • ThreadLocal
        • Multitheading If
        • Division
    • JVM
      • Class & Instance Initialization
      • Runtime Data Area
      • Garbage Collection
    • Web Container
      • Tomcat Architecture
      • Jetty Architecture
    • Spring
    • Tuning
      • Programming
  • Computer Science
    • Computer Organization
    • Algorithm
      • Complexity
      • Linear List
      • Sort
      • Binary Search
      • Skip List
      • Hash Table
      • Tree
      • Graph
      • String Matching
      • Bloom Filter
      • Greedy Algorithm
      • Divide and Conquer
      • Back Tracking
      • Dynamic Programming
    • Network Protocol
      • Pysical Layer
      • Data Link Layer
      • Network Layer
      • Transport Layer
      • Application layer
      • HTTP
      • HTTP/2 in Action
    • Operating System
      • Basic
      • System Initialization
      • Diagnostic Tools
      • CPU Diagnosis
      • Memory Diagnosis
      • Disk Diagnosis
      • Network Diagnosis
      • Monitor System
    • Design Patterns
      • UML
      • OOP
      • Principle
      • Refactoring & Specification
      • Creational
        • Singleton
        • Factory
        • Builder
        • Prototype
      • Structural
        • Proxy
        • Bridge
        • Decorator
        • Adapter
        • Facade
        • Composite
        • FlyWeight
      • Behavioral
        • Observer
        • Template Method
        • Strategy
        • State
        • Iterator
        • Chain of Responsibility
    • Distributed System
      • Protocol & Algorithm
      • Transcation
      • Theory
      • Resource Management
      • Scheduling
      • Computing
      • Message Queue
      • Cache
      • Consistent Hashing
  • database
    • InfluxDB
      • In-Memory Index
      • Meta
    • MySQL
      • SQL
      • Architecture
      • Log
      • Transaction
      • Indexing
      • Lock
      • Storage
    • Redis
    • Elasticsearch
      • Local Debug
    • HBase
    • Kafka
    • ZooKeeper
  • Reading
    • RocketMQ
    • 演说之禅
    • So Good They Can't Ignore You
    • 学会提问
    • Lecture
  • Other
    • v2ray
    • Kubernetes
    • Git
    • Maven
    • Anaconda And Conda
    • Fuck! Shit!
      • Remove Final by Reflection
      • Ingress Host
      • ExecuterService submit
  • Open source contribution
Powered by GitBook
On this page

Was this helpful?

  1. database
  2. MySQL

Storage

PreviousLockNextRedis

Last updated 5 years ago

Was this helpful?

和 的索引结构我们已经介绍,但是它们是怎么在磁盘上存储的呢?

记录是按照行存储的,但是读取的时候并不是以行为单位。在数据库中,无论读多少行,都是将这些行所在的页加载。也就是说,数据库磁盘存储的基本单位是页(Page)。

如下图,一个表空间包含一个或多个段,一个段包含一个或多个区,一个区包含了多个页,一个页有多行记录。

表空间(Tablespace)是一个逻辑容器,与段是 1:n 的关系。数据库由一个或多个表空间组成,从管理上可分为系统表空间、用户表空间、撤销表空间、临时表空间。查看表空间类型:

# ON 表示每张表会单独保存为一个 .ibd 文件
show variables like 'innodb_file_per_table';

段(Segment)与区是 1:n 的关系,段不要求区与区之间是连续的。当我们创建数据表、索引的时候,会创建相应的段,比如表段、索引段。

区(Extent)在 InnoDB 引擎中,一个区会分配 64 个连续的页,所以区的默认大小是 64 * 16KB = 1MB。

页(Page)存储多行记录,在 InnoDB 中默认大小为 16KB。按照类型分的话,常见的有数据页(保存 B+树的节点)、系统页、Undo 页、事务数据页等。查看页的大小:

show variables like '%innodb_page_size%';

数据页包含 7 个部分,如下图:

  • 文件通用部分:文件头(File Header)和文件尾(File Tailer),类似包装盒,将页的内容包装起来,通过文件头和文件尾检验的方式来确保页传输是完整的。

    • 文件头中有两个字段,FIL_PAGE_PREV 和 FIL_PAGE_NEXT,分别指向上一数据页和下一数据页,相当于双向链表。所以一个区中 64个页是逻辑上的连续,而不是物理上的。

    • 文件头给出 checksum ,到文件尾的时候整体运算出 checksum,两者一致才说明整个页传输是完整的。

  • 记录部分:最大最小记录(Infimum+supremum)、用户记录(User Records)、空闲空间(Free Space)占用了页结构的主要空间。当有新的记录插入时,会从空闲空间中进行分配存储。

  • 索引部分:指页目录(Page Directory),用户记录的目录,由于用户记录是顺序存储的,所以检索效率不高,有了页目录,就有二分查找的方式。如下图:

  1. 一个数据页中所有记录分成几组,不包括已删除记录。

  2. 第一组:最小记录,只包含一条;最后一组:包含最大记录,1-8条记录;其他组:4-8条记录。

  3. 每个组的最后一条记录中的头信息会存储该组有多少条记录,n_owned 字段。

  4. 页目录存储每组最后一条记录的地址偏移量,每组的地址偏移量叫做槽(slot),每个槽指向不同组的最后一条记录。

我们看看怎么进行二分查找,比如我们要查找主键为 9 的记录:

  1. low = 0, high = 4, (0 + 4) / 2 = 2,2 对应的最大记录为 8。

  2. 9 > 8,所以 low = 2, high = 4, (2 + 4) / 2 = 3,3 对应的最大记录为 12。

  3. 9 < 12,所以在槽 3 中进行查找,遍历槽 3,找到 9。

B+ 树与页的关系

  • 在 B+ 树中,每个节点都是一个页。

  • 同一层上的节点通过数据页中文件头的两个指针形成一个双向链表。

  • 非叶子节点有多个索引行,每个索引行存储索引键和指向下一层页面的数据页指针。

  • 叶子节点,存储了关键字和行记录,在数据页内部的多条记录是一个单向链表。通过对页目录进行二分查找。

B 树
B+ 树