mysql B+Tree

基本模型

InnoDB 的数据是按「数据页」为单位来读写的，也就是说，当需要读一条记录的时候，并不是将这个记录本身从磁盘读出来，而是以页为单位，将其整体读入内存。数据库的 I/O 操作的最小单位是页，InnoDB 数据页的默认大小是 16KB，意味着数据库每次读写都是以 16KB 为单位的，一次最少从磁盘中读取 16K 的内容到内存中，一次最少把内存中的 16K 内容刷新到磁盘中。

插入记录时保证主键的大小顺序，下图黄色框里的为主键

当一页存不下的时候就需要存储到新的页中，页号并不一定是连续的，他只要保证通过一个地址能找到即可。

上图中，因为要满足主键大小顺序，所以28页中的那条数据主键为4，要和页10中主键为5的记录进行交换，这叫做记录移动。

如果要在这种结构中去查找一条记录，还是只能从头开始访问到尾，因此有了目录项，记录每页的最小的值，和页号。我们将目录项连续存储，这样在如果要找主键20的这个记录，就先从目录项开始找，二分法直接确定是在目录项3中，其他的页就都可以不用考虑了。然后因为数据项都是有序存储的，所以再针对页9做二分法来查找。

这里有一个问题，数据页中的记录是按照单向链表来存储的，要如何进行二分法来查找？

这就涉及到页的结构。每个数据页中会将数据进行分组，然后用一个叫页目录的东西来记录每个分组中最大的那条记录的地址偏移量，这些偏移量被称作槽（slot），这些槽就相当于分组记录的索引。

然后通过槽来进行二分查找，确定数据在哪个分组中，然后再去该组中进行查找。但是组中的数据也依然是按照单项链表来存储的啊，那不还是O(n)吗？每组的记录条数是有规定的，这样即使是一条条查找也没有什么问题：

• 第一个分组中的记录只能有 1 条记录；
• 最后一个分组中的记录条数范围只能在 1-8 条之间；
• 剩下的分组中记录条数范围只能在 4-8 条之间。

针对数据项做的简易目录就搞定了，这个目录有一个别名，称为索引。

迭代1

上面的基本模型，将目录项存放在连续空间上，这样通过二分法就能很快定位。但是还是因为一些数据的增删操作，使得连续空间来存储目录项是不靠谱的。因此还是只能考虑和数据页一样，通过链表来组织。为了描述方便讲目录项构成的页称之为目录页，实际他们都是属于数据页的。

整体结构跟数据页差不多，为了区分，用record_type=1来表示目录页。

两者都会为主键值生成Page Dirctory（页目录），从而按照主键值进行查找时可以使用二分法来加快查询速度。比如说要找值为20的这条记录，先从目录页中按照二分法很快找到应该在页9，然后到页9中继续通过该页的页目录按照二分法找到20这条记录。这个过程磁盘i/o只有两次，一次是加载目录页，一次是加载页9。

迭代2

当页目录增加的也会面上面同样的问题，得一个个找，很可能找到最后才找到。这时，当页目录达到两个及以上的时候就再加一层来管理页目录。

最后就是这么一个结构，这就是B+Tree

B+Tree通过不会超过4层，因为4层已经能存放很多数据了，且层越多io也越多。