面试题

No.23：B+ 树是如何组织数据的？

页是 MySQL 中数据存储的基本单元，整颗 B+ 树就是一个又一个相互使用指针连接在一起的页组成的。

图 8-11 展示出了页之间的指针关系：

1. 上层页对下层页拥有单向指针
2. 同一层内相邻的页之间拥有双向指针，无论是上面的索引页层还是底层的数据页层
3. 最底层数据页层中，每一页可以存储多行数据，每一行数据拥有指向下一行的单向指针

No.24：InnoDB 为什么适合存储大量数据行？

InnoDB 的多级二叉树把数据进行了非常扁平的多级索引，三层索引就可以存储 2100 万行数据，非常适合在行数特别多的时候进行单个数据的读取和写入。在存储大量数据行时，InnoDB 拥有如下几个优势：

1. 数据访问效率高：InnoDB 使用 B+ 树作为索引结构，这种平衡的多路搜索树具有良好的层次性，在查询大量数据时能提高数据访问效率。
2. 顺序访问性能好：B+ 树的叶子节点使用链表连接，使得范围查询和顺序访问操作非常高效，减少磁盘 IO 次数，提升读取性能。
3. 支持高并发和事务：InnoDB 支持事务，B+ 树在并发访问场景下有较好的性能表现，使用多版本并发控制（MVCC）机制，提供高度并发性并保证数据的一致性和隔离性。
4. 空间利用率高：B+ 树具有较高的空间利用率，非叶子节点只存储关键字信息，叶子节点存储实际数据和指针，减少存储空间的浪费。

No.25：缓存 LRU 算法是什么，InnoDB 又做了哪些优化？

缓存 LRU（Least Recently Used）算法是一种常用的缓存替换算法，用于确定哪些数据应该从缓存中淘汰。其原理是基于数据的访问时间，最近被使用过的数据将具有较高的访问概率，而较长时间未被使用的数据则可能不再需要。

InnoDB 在缓存 LRU 算法上进行了一些优化：

1. 脏页刷新机制：InnoDB 使用了缓冲池（buffer pool）来缓存数据页，当数据页发生修改时会被标记为脏页。InnoDB 通过脏页刷新机制，将脏页异步写入磁盘，以减少 I/O 操作的等待时间，提高性能。
2. 自适应哈希索引：在 InnoDB 中，数据页可以通过哈希索引进行快速查找。InnoDB 会根据数据页的访问模式自动调整哈希索引，以提高数据访问效率。
3. 随机 I/O 优化：InnoDB 通过顺序扫描和预读取机制，降低了随机 I/O 的频率。它可以通过读取连续的数据页来利用磁盘的预读取特性，减少了访问数据的磁盘IO次数。
4. LRU 链长调整机制：InnoDB 会根据系统的访问模式动态调整 LRU 链的长度，以适应不同的工作负载。这可以提高缓存命中率，减少不必要的缓存替换操作。

No.26：多少行数据以后需要分库分表？

在单行数据为 0.9KB 的情况下，当数据量达到 2100 万行时，InnoDB 的 B+ 树会从三层变为四层。然而，这个转变并不是分库分表的依据。在内存容量足够的情况下，跨越临界点前后的 InnoDB 几乎没有性能差别。

相反，以下策略对于数据库优化来说更有价值：

1. 对于单行数据较大的表进行横向分表。对于行数超过 50 万行的表来说，建议将单行数据限制在 2KB 以内。
2. 对于经常更新和删除数据的表，应该定期执行 B+ 树重整操作。通过执行 recreate + analyze 操作可以显著提升性能。
3. 从业务角度来看，如果可能的话，尽量避免分表——过早优化是万恶之源。