存储单元

存储器范围比较大，但是数据具体怎么存储，有自己的最小存储单元。

1.数据持久化存储在磁盘里，磁盘的最小单元是扇区，一个扇区的大小是512个字节
2.文件系统的最小单元是块，一个块就是4K
3.InnoDB存储引擎，有自己的最小单元，称之为页，一个页大小是16K。

扇区、块、页三者之间的关系：
image.png

InnoDB引擎

如果mysql部署在本地，通过命令方式连接mysql，默认端口为3306，然后输入密码即可进入

  1. mysql -u root -p

查看InnoDB的页大小

show variables like 'innodb_page_size';

image.png
mysql数据库中，table表中的记录都是存储在页中，那么一页可以存多少行？假如一行数据的大小为1K字节，那么按16K/1K=16,可以计算出一页大约能存放16条数据。
mysql的最小存储单元叫做”页”，这么多页是如何构建一个庞大的组织，我们如何知道数据存储在哪一个页中？
如果逐条遍历，性能差，为了提升速度，我们引入了B+树
image.png
页除了可以存放数据（叶子节点），还可以存放键值和指针（非叶子节点），他们是有序的。这样的数据组织形式，我们称之为索引组织表。

如：上图中 page number=3的页，该页存放键值和指向数据页的指针，这样的页由N个键值+指针组成

B+树是如何检索记录？

  • 首先找到根页，你怎么知道一张表的根页在哪？
  • 其实每张表的根页位置在表空间文件中是固定的，即page number=3的页
  • 找到根页通过二分查找法，定位到id=5的数据应该在指针P5指向的页中
  • 然后再去page number=5的页中查找，同样通过二分查询法即可找到id=5的记录

    如何计算B+树的高度？

    在InnoDB 的表空间文件中，约定page number = 3表示主键索引的根页
    SELECT
b.name, a.name, index_id, type, a.space, a.PAGE_NO
FROM
information_schema.INNODB_SYS_INDEXES a,
information_schema.INNODB_SYS_TABLES b
WHERE
a.table_id = b.table_id AND a.space <> 0
and b.name like '%sp_job_log';
    00b26abe9fc662a249c3ff7d13d58e24.png

    从图中可以看出，每个表的主键索引的根页的page number都是3，而其他的二级索引page number为4

在根页偏移量为64的地方存放了该B+树的page level。主键索引B+树的根页在整个表空间文件中的第3个页开始，所以算出它在文件中的偏移量：16384*3 + 64 = 49152 + 64 =49216，前2个字节中。
首先，找到MySql数据库物理文件存放位置：

show global variables like "%datadir%" ;

image.png
hexdump工具，查看表空间文件指定偏移量上的数据：

hexdump -s 49216 -n 10  sp_job_log.ibd

Mysql一棵B 树能存多少条数据 - 图6
page_level 值是 1，那么 B+树高度为 page level + 1 = 2

特别说明：

  • 查询数据库时，不论读一行，还是读多行，都是将这些行所在的整页数据加载，然后在内存中匹配过滤出最终结果。
  • 表的检索速度跟树的深度有直接关系，毕竟一次页加载就是一次IO，而磁盘IO又是比较费时间。对于一张千万级条数B+树高度为3的表与几十万级B+树高度也为3的表，其实查询效率相差不大。

    一棵树可以存放多少行数据？

    假设B+树的深度为2
    这棵B+树的存储总记录数 = 根节点指针数 单个叶子节点记录条数
    那么指针数如何计算？
    假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节。
    那么一个页中能存放多少这样的组合，就代表有多少指针，即 16384 / 14 = 1170。那么可以算出一棵高度为2 的B+树，能存放 1170     16 = 18720 条这样的数据记录。
    同理：
    高度为3的B+树可以存放的行数 = 1170 1170 16 = 21902400

    千万级的数据存储只需要约3层B+树，查询数据时，每加载一页（page）代表一次IO。所以说，根据主键id索引查询约3次IO便可以找到目标结果。

对于一些复杂的查询，可能需要走二级索引，那么通过二级索引查找记录最多需要花费多少次IO呢？
image.png
首先，从二级索引B+树中，根据name 找到对应的主键id
image.png
然后，再根据主键id 从 聚簇索引查找到对应的记录。如上图所示，二级索引有3层，聚簇索引有3层，那么最多花费的IO次数是：3+3 = 6
聚簇索引默认是主键，如果表中没有定义主键，InnoDB 会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB 会隐式定义一个主键来作为聚簇索引。

这也是为什么InnoDB表必须有主键，并且推荐使用整型的自增主键！！！ InnoDB使用的是聚簇索引，将主键组织到一棵B+树中，而行数据就储存在叶子节点上

举例说明：
1、若使用”where id = 14”这样的条件查找记录，则按照B+树的检索算法即可查找到对应的叶节点，之后获得行数据。
2、若对Name列进行条件搜索，则需要两个步骤：

  • 第一步在辅助索引B+树中检索Name，到达其叶子节点获取对应的主键值。

  • 第二步使用主键值在主索引B+树中再执行一次B+树检索操作，最终到达叶子节点即可获取整行数据。（重点在于通过其他键需要建立辅助索引）

    实战演示

    实际项目中，每个表的结构设计都不一样，占用的存储空间大小也各不相等。如何计算不同的B+树深度下，一个表可以存储的记录条数？
    我们以业务日志表 sp_job_log 为例，讲解详细的计算过程：
    1、查看表的状态信息
    show table status like ‘sp_job_log’\G
    Mysql一棵B 树能存多少条数据 - 图9
    图中看到sp_job_log表的行平均大小为153个字节
    2、查看表结构
    desc sp_job_log;
    Mysql一棵B 树能存多少条数据 - 图10
    3、计算B+树的行数

  • 单个叶子节点（页）中的记录数 = 16K / 153 = 105

  • 非叶子节点能存放多少指针， 16384 / 14 = 1170
  • 如果树的高度为3，可以存放的记录行数 = 1170 1170 105 = 143,734,500

参考文献：https://blog.csdn.net/g6U8W7p06dCO99fQ3/article/details/117608254