MySQL中InnoDB引擎逻辑存储结构、B+树索引结构、B+树高度及存储数据量

InnoDB逻辑存储结构

• 表空间：InnoDB存储引擎逻辑结构的最高层，如果用户启用了参数innodb_file_per_table（在8.0版本中默认开启），则每张表都会有一个表空间（xxx.ibd），一个mysql实例可以对应多个表空间，用于存储记录、索引等数据
• 段：表空间是由各个段组成的，常见的段有数据段（Leaf node segment）、索引段（Non-leaf node segment）、回滚段（Rollback segment）等。InnoDB是索引组织表，数据段就是B+树的叶子节点，索引段即为B+树的非叶子节点。InnoDB中对于段的管理，都是引擎自身完成，不需要人为对其控制，一个段中包含多个区
• 区：区是表空间的单元结构，每个区的大小为1M。默认情况下，InnoDB存储引擎页大小为16K，即一个区中一共有64个连续的页
• 页：页是组成区的最小单元，页也是InnoDB存储引擎磁盘管理的最小单元，每个页的大小默认为16KB。为了保证页的连续性，InnoDB存储引擎每次从磁盘申请4-5个区
• 行：InnoDB存储引擎是面向行的，也就是说数据是按行进行存放的，在每一行中除了定义表时所指定的字段以外，还包含两个隐藏字段
  • Trx_id：每次对某条记录进行改动时，都会把对应的事务id赋值给trx_id隐藏列
  • Roll_pointer：每次对某条记录进行改动时，都会把旧的版本写入到undo日志中，然后这个隐藏列就相当于一个指针，可以通过它来找到该记录修改前的信息

关于树的概念：二叉树、二叉查找树、二叉树遍历、平衡二叉树、红黑树及其自旋规则、B-Tree、B+Tree

MySQL中优化之后的B+Tree

• MySQL索引数据结构对经典的B+Tree进行了优化

• 在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree

• 提高区间访问的性能，利于排序

  

为什么InnoDB存储引擎选择B+Tree索引结构

• 相对于二叉树，层级更少，搜索效率高
• 对于B-Tree，无论是叶子节点还是非叶子节点都会保存数据，这样导致一页中存储的键值减少，指针跟着减少，要同样保存大量数据，只能增加树的高度，导致性能降低
• 相对Hash索引，B+Tree支持范围匹配及排序操作

InnoDB主键索引的B+Tree高度为多高呢？能存储多少条数据呢？

• 假设：一行数据大小为1k，一页中可以存储16行这样的数据。InnoDB的指针占用6个字节的空间，主键假设为bigint占用8个字节
• 高度为2时：
  • n*8+(n+1)*6=16*1024，算出n约为1170，也就是根节点可以存1170个key
  • 1171*16=18736
  • 也就是说，如果数的高度为2，则可以存储18000多条记录
• 高度为3时：
  • 1171*1171*16=21939856
  • 也就是说，如果树的高度为3，则可以存储2200w左右的记录