B树

b树范围查找需要不断的回到非叶子节点上

好处是

  • 线性数据结构和树的结合
  • 通过多数据节点大大降低了树的高度
  • B树不需要旋转就可以保证树的平衡

image.png

B+树

叶子节点是前后链表, 范围查找方便
所有数据都在叶子节点都在叶子节点
所有数据形成一个线性表
image.png

真实的b+树, I和S代表上下限指针
同一层还有互相指针指向过去
b+树的节点就叫做page
第一行: 大于等于0的去4号页去找, 去磁盘读取4号页,
4号页有I和S指针, I代表大于等于0的去6号页去找
6号页下限指针就是指向了数据, 不像上面指向范围了
image.png
查找数据id为1的怎么查?
第一层: (>=0 ->4), 大于等于0到page 4,
page4里面有(>=0, ->6)到page 6里面查找
page 6里面是(0 A),(1,B)
先扫id为0, 给server发现不对, 再往下找

查id>=1, <=5的 , 找到page 6的(1 B), 然后里面有个S上限指针, 通过这个上限指针找到下个页page7 挨个找过去.

在优化后，树的第一层一定在内存中，而第二层也大概率在内存中，所以查找数据时磁盘平均的访问次数并不高（InnoDB 还有页缓存）。 一旦数据被定位到某个页后，将其加载到内存中，由于页内的数据是有序的，所以可以使用类似于二分法的方式访问整个页的数据，从而达到快速查询到所需数据的目的。由于 B+ 树在读写上的性能优势，以及适配磁盘的访问方式，其在数据库引擎领域已被广泛应用。

联合索引

里面隐式包含主键id
首先按照最左侧这个字段排序
image.png

逻辑存储结构

分为: 表空间, 段, 区, 页, 行
innodb的页是自己的概念和硬件的页无关

表空间是.ibd文件
page就是B+树上的page
Trx id是事务id, 表示是那个事务更新的
Coln是行数据
image.png

表空间

  • 表空间指的是数据表在硬盘上的存储空间
  • 默认, 所有的表数据都存在共享表空间
  • 每个表的数据也可以放在独占表空间(.ibd文件)

    段

    数据段: B+树的叶子节点
    索引段: B+树的非叶子节点
    innodb中, 段由innodb自己管理的
    image.png

区(Extent)

  • 一个区默认64个page, 每个page默认16K, 16KB * 64 = 1M
  • 区是由连续页区间组成的空间, 大小为1MB

  • 一次从磁盘申请4~5个区, 避免区过于碎片化

    页(page)

    页是innodb中磁盘读写的最小逻辑单位, 默认16KB
    一个数据页就是一个B+树的节点(B+ Tree Node)
    页的大小充分考虑了机械磁盘和SSD的最小读写单元(512B和4KB)
    image.png

    变长列

  • 长度不固定的数据类型: varchar, varbinary, blob, text

  • 占用空间大于768Byte的不变长类型: char (大于768Byte就是变长的了)

  • 变长编码下的char (编码不同造成不同, 比如utf8一个字符占磁盘空间是不同的)

    行溢出数据

  • 由于innodb每个数据页容量有限, 导致数据字段也是有限的

  • 当数据字段过大时, innodb会使用行溢出机制
  • 行溢出机制会把超长字段放入单独开辟的数据页

image.png
转换成行溢出, 不然把大的行放在里面, 每次取页, 页里面都是这个大的行数据, 把大的行数据单独放在外面
image.png

行记录格式(Row Format)

主要分为两个时代

  • Redundant/Compact (Antelope文件格式) 老的
  • Dynamic/Compressed (Barracuda文件格式)

进化的核心需求是节约行记录空间, 从而增加每个页的数据行数, 提高查询效率

Redundant

冗余的
mysql5.0之前, 默认的
image.png

  • 字段偏移列表告诉你, 每个字段偏移了多少, 按照列的顺序逆序放置
  • Header: 列数量, 字段偏移表的单位, 下一行记录的指针等等
  • RowID: 没有可用主键的时候, 使用RowID作为隐藏主键
  • TxID: 事务id
  • Roll Pointer: 回滚指针
  • Col1 这边没出现数据溢出

溢出了怎么办?
image.png
存前768Byte数据, 然后跟个BLOB页指针

Compact

mysql5.1默认row format
相比较redundant的字段偏移列表,改进了下, 里面有定长的字段, 那从固定多少读就行, 不用字段偏移列表记录那么多信息
image.png

  • 变长字段长度表: 每个变长字段的长度, 按照列的顺序逆序放置, 只记录变长的, 定长的没必要记录, 改进的点
  • null标志位: 表示里面的null的列, 不然要把这个null的列放在变长字段表里面, 从哪开始到哪里结束, 而这个标识位用bit代表一个字段就行
  • Header: 列数量, 下一行记录的指针等信息

    Dynamic

    mysql5.7之后默认row format
    image.png
    长度大于40个字节的时候不放在col里面了, 直接溢出, 这样查询的效率更高
    动态是在col有时候是数据, 有时候是指针

    Compressed

    image.png
    压缩的意思, 物理结构和Dynamic类似
    对表的数据用zlib进行了压缩存储, 可以节省40%的空间, 但是对cpu压力比较大