Week_09 总结

mysql 数据库基本原理

客户端 =》 连接处理 =》 语法解析 =》存储引擎 =》 文件系统 =》磁盘

InnoDB 记录存储结构

• InnoDB 是以行的方式将数据存储在磁盘上的

• 有四种行格式

• compact

• redundant

• dynamic

• compressed

compact

创建数据表时，可指定行格式

mysql> CREATE TABLE record_format_demo (    ->     c1 VARCHAR(10),    ->     c2 VARCHAR(10) NOT NULL,    ->     c3 CHAR(10),    ->     c4 VARCHAR(10)    -> ) CHARSET=ascii ROW_FORMAT=`COMPACT`;Query OK, 0 rows affected (0.03 sec)

以行格式进行存储

• 变长字段长度列表：存储 varchar，varbinary 等 text 或者 blob 类型的列数据长度信息，以逆序排列

• NULL 值列表：列中的数据为 NULL，用 bit 位来表示允许为空的列是否为空，节省存储空间

• 记录头信息：该行相关的属性信息（该页中第几条记录，下一条记录的偏移，是否已删除等标识），方便管理

• 其他部分：实际的数据

redundant

mysql5.0 以前使用的格式

• 会记录每列值的长度偏移

• 偏移列表中用一个 bit 位表明该列是否为 NULL

dynamic

mysql5.7 版本默认行格式是 dynamic 格式，大体与 compact 一致，处理溢出列时有差异

• compact 会在行中记录溢出列数据的前 768 个字节，后 20 字节指向溢出页的地址

• dynamic 直接记录指向溢出页的地址

compressed

与 compact 大体一致，对溢出页会使用压缩算法进行压缩，以节省空间。

InnoDB 数据页结构

InnoDB 将数据划分成若干页，每页大小是 16KB，与磁盘交互时，每次读写至少 16KB 的数据

• FileHeader：页的通用信息。页号，上一页，下一页，页类型，属于哪个表，是不是溢出页等

• PageHeader：页的专用信息。页目录中有多少个 slot，空闲空间的偏移地址等

• 最大记录与最小记录：页中记录形成单链表的头和尾，这个链表是以主键进行排序的有序链表，对表的插入与删除都会维护这个有序单向链表

• 空闲空间：未使用的空间

• 页目录：对页中数据行进行分组，存储每组中 key 最大行的偏移，类似于对单向链表进行跳表设计。查找具体行时，更快

• FileTrailer：有校验码，用于数据校验。防止该页写了一半后，由于断电等因素，数据未全部落盘，造成数据的不完整

InnoDB 快速查询的秘密

页内查找

通过单向链表+目录页（跳表）的方式使用二分查找快速定位数据行。

页间查找

InnoDB 中页与页之间构成了双向链表，查找过程如下：

• 定位记录所在页

• 从页内查找

为了更快速的从页双向链表中，找到记录所在页，通常做法是为页中主键最小或者最大的行做个目录映射表，表明该主键对应的行数据在哪页

这个主键与页号的映射表也记录在一个页中，通过行的记录头信息的 record_type 来标明这是普通数据还是目录映射数据。

如果映射表多到一页放不下，那就拿俩页放，然后构成双向链表。如果更多，那就在这些映射表之上再次构建主键与页映射表，仍旧类似跳表那样。

最后整个结构构成一颗树，这棵树叶子节点是数据节点，非叶子节点是索引节点，各层通过有序链表进行连接，这样的结构就是 B+树。

假设每页中存储 100 行用户数据，每个目录页中存储 1000 个目录映射对

B+树有 1 层，存放 100 个行记录

B+树有 2 层，存放 1000*100 个行记录，10w 条记录

B+树有 3 层，存放 1000*1000*100 个行记录，1 亿条记录

因此数据量如果不超过这个规模，那只要进行 4 次页内查找，即可定位数据行

聚簇索引

• 使用主键进行页内记录和排序，组成单向链表

• 同一层中，使用主键进行页间记录和排序，组成双向链表

• 叶子节点存储所有数据

聚簇索引指的就是根据主键构建的 B+树，InnoDB 中存储引擎会自动创建聚簇索引，不论是否设置主键

非聚簇索引

以主键进行查找时，通过聚簇索引可以快速找到数据。对于以非主键的列进行查找时，查找过程如下：

• 定位该列对应主键

• 通过主键定位数据行

非聚簇索引指通过构造指定列与主键映射关系，叶子节点存储映射关系，以列值作为 key 而形成的 B+树

合理使用索引

1. 只为用于搜索排序或者分组的列建索引（where,order by, group by）

2. 列中值不重复的个数。大量重复值的列建索引会导致太多的回表操作

3. 索引列或者主键的类型尽量小，避免索引节点占用大量空间，降低磁盘 io 的性能损耗

4. 尽量使用覆盖索引（索引中已包含要读取的列），不能简单用*代替，尽可能减少回表操作

5. 索引列在搜索条件中以单独形式出现，避免全表扫描

6. 主键插入时不要忽大忽小，这种情况下，容易造成聚簇索引发生页面分裂，有性能损耗

7. 删除冗余重复索引

java 虚拟机

• jvm 类似于计算机，有程序执行堆栈，相应的寄存器，代码段，cpu 计算单元等， 不同之处是 jvm 的指令集是字节码指令，计算机是相应的汇编指令。

• 当启动 java 程序时，会启动一个 jvm 进程，该进程通过类加载器加载相应的类文件，将类放入方法区，并启动相应线程，设置线程栈，同时将数据放入堆中，设置程序寄存器，由执行引擎执行方法区中字节码指令。

• 静态变量和方法的存储在方法区，运行时的对象是在堆中分布，每个线程有一个自己的栈，存放函数内局部变量

• java 的内存模型，各个 java 线程访问的是 numa 结构中对应 cpu 的 cache，各个 cpucache 数据更改后需要同步到主内存，java 中通过 volatile 来保证工作内存中值的修改会同步到主内存，使各 java 线程不出现数据不一致的问题

java 虚拟机的垃圾回收

对共享的数据区（堆）中的不在使用的对象进行回收。

回收策略

1. 标记

• 从线程栈中的局部变量找

• 从方法区的静态变量找

• 从上述找到的对象中查看是否有其他对象的引用，有则标记

• 标记了表示不能被回收，否则可回收

1. 清除

• 清理：清除垃圾对象，将其内存放入空闲列表，以便后续分配使用

• 压缩：将清除后出现空洞的堆空间，进行压缩。（将存活对象拷贝到连续空间内，保证堆空间的连续性）

• 复制：将堆空间分成 2 块，一块用于创建对象，当这块空间用完后，将其中还活着的对象复制到另一个空间，完成清除工作

分代垃圾回收

java 以复制的方式进行垃圾回收，具体回收过程如下：

1. 将堆内存分为两大部分：新生代和老年代

2. 新生代中又分为：Eden 区，From 区，To 区

3. 对象内存分配时，在 eden 区进行分配

4. 当 eden 区对象内存分配达到一定比例或者满时，触发垃圾回收

5. 将 eden 区无用对象进行回收，剩余有用对象被复制到 From 区，然后清空 eden 区

6. 第一次回收结束，程序继续运行

7. 新的对象又在 eden 区中产生，且再次触发 gc，重复上述步骤

8. 如果 From 区放不下时，将 Eden 和 From 区所有对象都复制到 To 区，同时清空 Eden 区和 From 区

9. 第二次回收结束，程序继续运行

10. eden 区再次触发 gc，此时会将 eden 和 to 区对象复制到 from 区，清空 eden 和 to 区

11. 第三次回收结束，程序继续运行，重复往返的执行上述过程

12. 如果有些对象在多次 gc 后，还 From 区或者 To 区存在，则说明该对象生命周期长，将这些对象复制到老年代

13. 当老年代空间也满时，触发一次新生代和老年代的全量 gc

垃圾回收算法

• 串行回收器：应用程序并行执行，有 GC 时，挂起应用程序线程。然后启动一个垃圾回收线程进行回收，回收完毕后，应用程序线程继续执行

• 并行回收器：在多核时代，为了提高回收效率，用多个回收线程进行回收工作

• 并发回收器 CMS：将回收过程进一步细化，标记过程分为初始标记，并发标记，重标记，并发清理 4 个阶段。初始标记时，进行 stop the world，短时间内标记完。之后进入并发标记阶段，用户线程和 gc 线程同时运行。在并发标记的过程中，又有新的对象产生，之前标记的可能不准，因此进入重标记阶段。在该阶段，为了防止误删，会进行 stop the world。之后将标记好的进行并发清理

• G1 回收器：将 eden 区，from,to 区，老年期分的粒度更细，然后对这些区域进行控制，回收时，不必整块内存区去遍历