KV式数据结构
KV式数据应该是我们非常常见的一种数据结构。它的具体实现有散列表，各种二叉树，多叉数等。在散列表中，我们直接拿Key计算寻找到数据节点。在B树家族，红黑树，跳表中，我们通过遍历比对Key的大小拿到数据节点。总而言之，这些数据结构都遵循按照key的大小顺序组织排列数据节点，根据key的大小顺序找到所需的数据节点。
class dataNode{
int Key;
Object value;
}
常见数据结构.png
KV式数据如何落盘
顺序落盘
按照key的大小顺序落盘，这是一种简单便捷的一种落盘方式。这种情况下我们可以把数据快速的加载到内存，按照key的大小可以快速在内存顺序的构建一种数据结构。但是缺点也很明显，当我们插入的数据节点的key大小位于中位，那么之后的数据节点在磁盘中需要往后移动搬迁，需要大量的磁盘IO.
插入过程.png
一种独特的落盘方式
1.先把磁盘文件分页（假设每个页为4KB）。
2.在每个页内，数据节点直接尾插到最后。
3.再找一个文件记录这个数据文件的元数据，记录每个页的页号，每个页里的key的最大值和最小值（每个页的这个区间相互不交叉），以及每个页最后一个数据节点写到的位置。
磁盘分页
class dataMeta{
List<pageMeta> pageMetas;
}
class pageMeta{
//页号
int index;
int minKey;
int maxKey;
//该页的最后一个位置，后面的位置padding补\0
int Trailer;
}
4.插入过程：当我们插入一个数据节点时，我们先读取元数据，找到符合自己key的最大值和最小值区间的页号和这个页号对应的trailer(最后一个位置)，直接尾插写入，然后更新元数据文件。如下面几幅图片所示：
2022-10-04 17-30-22 的屏幕截图.png
2022-10-04 17-30-37 的屏幕截图.png
2022-10-04 17-31-04 的屏幕截图.png
2022-10-04 17-31-27 的屏幕截图.png
2022-10-04 17-32-07 的屏幕截图.png
2022-10-04 17-32-32 的屏幕截图.png
2022-10-04 17-32-53 的屏幕截图.png
5.查询过程，根据元数据的Key区间找到满足的区间的页号，遍历该页号的数据节点，比对key找到数据节点，时间复杂度O(n),当n为一个确定值时，O(n)=O(1)，这里的n等于页大小4KB=4096.
