「SQL」拜托，别再问我什么是 B+ 树了( 三 ) |数据结构|

内存放不下，我们可以把它放到磁盘嘛，磁盘空间比内存大多了，但新的问题又来了，我们知道内存与磁盘的读取速度相差太大了，通常内存是纳秒级的，而磁盘是毫秒级的，读取同样大小的数据，两者可能相差上万倍，于是上一步我们计算的 27 次查询如果放在磁盘中来看就非常要命了（查找一个节点可以认为是一次磁盘 IO ，也就是说有 27 次磁盘 IO！）， 27 次查询是否可以优化？
可以很明显地观察到查询次数和树高有关，那树高和什么有关，很明显和每个节点的子节点个数有关，即 N 叉树中的 N ，假设现在有 16 个数，我们分别用二叉树和五叉树来构建，看下树高分别是多少

本文插图

本文插图
可以看到如果用二叉树，要遍历 5 个节点，如果用五叉树，只要遍历 3 次，一下少了两次磁盘 IO ，回过头来看上文的一亿个节点，如果我们用 100 叉树来构建，需要几次 IO 呢

本文插图
可以看到，最多遍历五次（实际上根节点一般存在内存里的，所以可以认为是 4 次）！磁盘 IO 一下从 27 减少到了 5！性能可以说是大大提升了,有人说 5 次还是太多，是不是可以把 100 叉树改成 1000 或 10000 叉树呢，这样 IO 次数不就就能进一步减少了。
这里我们就需要了解页（page）的概念，在计算机里，无论是内存还是磁盘，操作系统都是按页的大小进行读取的（页大小通常为 4 kb），磁盘每次读取都会预读，会提前将连续的数据读入内存中，这样就避免了多次 IO ，这就是计算机中有名的局部性原理，即我用到一块数据，很大可能这块数据附近的数据也会被用到，干脆一起加载，省得多次 IO 拖慢速度，这个连续数据有多大呢，必须是操作系统页大小的整数倍，这个连续数据就是 MySQL 的页，默认值为 16 KB ，也就是说对于 B+ 树的节点，最好设置成页的大小（16 KB），这样一个 B+ 树上的节点就只会有一次 IO 读。
那有人就会问了，这个页大小是不是越大越好呢，设置大一点，节点可容纳的数据就越多，树高越小， IO 不就越小了吗，这里要注意，页大小并不是越大越好， InnoDB 是通过内存中的缓存池（pool buffer）来管理从磁盘中读取的页数据的。页太大的话，很快就把这个缓存池撑满了，可能会造成页在内存与磁盘间频繁换入换出，影响性能。
通过以上分析，相信我们不难猜测出 N 叉树中的 N 该怎么设置了，只要选的时候尽量保证每个节点的大小等于一个页（16kb）的大小即可。

本文插图
页分裂与页合并现在我们来看看开头的问题，为啥推荐自增 id 作为主键，自建主键不行吗，有人可能会说用户的身份证是唯一的，可以用它来做主键，假设以身份证作主键，会有什么问题呢。
B+ 树为了维护索引的有序性，每插入或更新一条记录的时候，会对索引进行更新。假设原来基于身份证作索引的 B+ 树如下（假设为二叉树，图中只列出了身份证的前四位）

本文插图
现在有一个开头是 3604 的身份证对应的记录插入 db，此时要更新索引，按排序来更新的话，显然这个 3604 的身份证号应该插到左边节点 3504 后面（如下图示，假设为二叉树）。