『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+ 树如下（假设为二叉树， 图中只列出了身份证的前四位）
本文插图
【『SQL』拜托，别再问我什么是 B+ 树了】
现在有一个开头是 3604 的身份证对应的记录插入 db， 此时要更新索引 ， 按排序来更新的话 ， 显然这个 3604 的身份证号应该插到左边节点 3504 后面（如下图示 ， 假设为二叉树） 。
推荐阅读
- ■面试官求你了，别再问我HTTPS
- @原创 别再看不起千元机，这4款好评度高过旗舰，最低仅999起！
- 【婷小姐】原创 别再看不起千元机，这4款好评度高过旗舰，最低仅999起！
- 『手机大魔王』别再被骗了，iphone6S真不卡，能再战5年？网友：自欺欺人罢了
- 【比特币】挖出来的币都值钱吗？别再浪费时间了
- 『即时战略游戏』别再说玩游戏浪费时间，国外研究玩游戏能锻炼视觉反应力
- 卡顿@手机卡顿影响使用，原因不过就是这3点，别再傻傻换新机了！
- 手机：别再说5G手机贵 备好3000元就能拥有它们
- 「」别再浪费时间修图了！一键出片它不香吗？
- [用户]90后上珍爱网玩线上相亲了？让爸妈别再蹲相亲角了！