第6章 数据库

6.1 范式与反范式

数据库范式要求

虽然范式不一定要遵守，但还是需要仔细权衡。

6.2 分库分表

6.2.1 为什么要分

分库的目的是做“业务拆分”，通过业务拆分，把一个大的复杂系统拆成多个业务子系统，之间通过RPC或消息中间件通信。这样做既便于团队成员的职责分工，也便于对未来某个系统进行扩展。

第二个考虑是应对高并发，读少写多，或者说写入的 QPS己经达到了数据库的瓶颈，这时就要考虑分库分表了。

另外一个考虑角度是“数据隔离”，这样避免业务之间相互影响。

6.2.2分布式ID生成服务

在分库之前，数据库的自增主键可以唯一标识一条记录，在分库分表之后，需要一个全局的ID生成服务，如雪花算法（Snowflake）。

6.2.3拆分维度的选择

有了全局的ID，接下来的问题是按哪个维度进行拆分。对于在分库分表之后其他维度的查询，一般有以下几个方法：

• 建立一个映射表：建立辅助维度和主维度之间的映射关系，先根据主维度获取倒辅助维度的数据，再根据获取到的数据去查询。但这里有个问题：映射表本身也需要分库分表，并且分库分表维度和订单表的分库维度还不同。并且，写入一条订单的时候也可能需要同时写两个库，属于分布式事务问题。
• 业务双写：同一份数据，两套分库分表，每套用各自的方法切分。同样，存在写入多个库的分布式事务问题。
• 异步双写：还是两套表，只是业务单写。然后通过监听Binlog，同步到另外一套表上。
• 两个维度统一到一个维度：把订单ID和用户ID统一成一个维度，比如把用户ID作为订单ID中的某几位；或者订单ID和用户ID中有某几位是相同的（两个ID都是字符串类型）， 用这几位作为分库维度。

6.2.4Join查询问题

分库分表之后，Join查询就不能用了，一般有下面几种解决方法：

• 把Join拆成多个单表查询，在代码层对结果进行拼装
• 做宽表，重写轻读
  需要把Join的结果分页，这需要利用MySQL本身的分页功能。 对于这种不得不用Join的情况，可以另外做一个Join表，提前把结果Join好。这是“重写轻读”, 其实也是“空间换时间”的思路。
• 利用搜索引擎
  可以利用类似ES的搜索引擎

6.2.5分布式事务

做了分库之后，纯数据库的事务就做不了了。一般的解决办法是优化业务，避免跨库的事务，保证所有事务都落到单库中。（比如说指定商户的数据一定在某个库之类的）如果实在无法避免，需要分布式事务的解决方案。

6.3 B+树

关系型数据库（B+树）在查询方面有一些重要特性，是KV型的数据库或者缓存所不具备的：

• 范围查询。
• 前缀匹配模糊查询。
• 排序和分页。

6.3.1 B+树逻辑结构

如图，是B+树的逻辑结构，有两个关键特征：

• 在叶子节点这一层，所有记录的主键都是按从小到大顺序排列，并且是一个双向链表，每个key对应一条记录
• 非叶子节点是叶子节点重key的最小值，都是冗余的，也是一个双向链表

数据库的主键对应的B+树的逻辑结构

基于此数据结构，关系型数据库的特性实现：

• 范围查询：如果要查[1,17]之间的记录，先找到1对应叶子节点，再找到17对应的叶子节点（16），然后顺序遍历即可
• 前缀模糊匹配：比如说查 where Key like abc% ，可以转化成一个范围查询 Key in [abc,abcz]
• 排序和分页：叶子节点天然就是排好序的，支持排序与分页

6.3.2 B+树物理结构

上面的树只是一个逻辑结构，最终要存储到磁盘上。下面以MySQL中最常用的InnoDB 引擎为例，看一下如何实现B+树的存储。

• InnoDB默认定义的块大小是16KB（innodb_page_size指定）
• 块是InnoDB读写磁盘的基本单位，InnoDB每一次磁盘I/O，读取的都是16KB的整数倍的数据
• 无论叶子节点，还是非叶子节点，都会装在Page里。InnoDB 为每个Page赋予一个全局的32位的编号，所以InnoDB的存储容量的上限是64TB(2^3xl6KB)

16KB是一个什么概念呢？如果用来装非叶子节点，一个Page大概可以装1000个Key(16K，假设Key是64位·整数，8个字节，再加上各种其他字段)，意味着B+树有1000个分叉；如果用来装叶子节点，一个Page大概可以装200条记录(记录和索引放在一起存储，假设一条记录 大概100个字节)。基于这种估算，一个三层的B+树可以存储多少数据量呢？

磁盘B+树示意图

第一层：一个节点是一个Page，里面存放了 1000个Key，对应1000个分叉。
第二层：1000个节点，1000个Page，每个Page里面装1000个Key。
第三层：1000x1000个节点(Page)，每个Page里面装200条记录，即是1000x1000x200 = 2亿条记录，总容量是16KBx1000x1000，约16GB。

Page与Page之间组成双向链表，每一个Page头部有两个关键字段：前一个Page的编号，后一个Page的编号。Page里面存储一条条的记录，记录之间用单向链表串联，最终所有的记录形成图6-1所示的双向链表的逻辑结构。对于记录来说，定位到了 Page,也就定位到了 Page 里面的记录。因为Page会一次性读入内存，同一个Page里面的记录可以在内存中顺序查找。

在InnoDB的实践里面，其中一个建议是按主键的自增顺序插入记录，就是为了避免Page Split问题。另外一个点，如果只是插入而不硬删除记录（只是软删除），也会避免某个Page的记录数减少进而发生相邻的Page合并的问题。

6.3.3非主键索引

对于非主键索引，同上面类似的结构，每一个非主键索引对应一颗B+树。在InnoDB中， 非主键索引的叶子节点存储的不是记录的指针，而是主键的值。所以，对于非主键索引的查询，会查询两棵B+树，先在非主键索引的B+树上定位主键，再用主键去主键索引的B+树上找到最终记录。

有一点需要特别说明：对于主键索引，一个Key只会对应一条记录；但对于非主键索引， 值可以重复。

非主键索引B+树示意图

首先，每个叶子节点存储了主键的值；对于非叶子节点，不仅存储了索引字段的值，同时也存储了对应的主键的最小值。