bplus_tree.cpp

/***
 * B+树的前世今生
 * MySql数据库索引是如何实现的
 * 为了加速数据库中数据的查找速度，常用的处理思路是对表加索引
 * 数据库索引是如何实现的？
 * 底层使用的是什么数据结构和算法？
 * 
 * 1. 解决问题的前提是定义清楚问题，对一些模糊的需求进行假设来限定要解决的问题范围
 * > 执行效率和存储空间
 * 执行效率高，存储空间低
 * 尝试几个数据结构来解决这个问题
 * 1. 散列表，O(1)查找，但是不支持区间快速查找数据
 * 2. 平衡二叉查找树 O(logn) 但是也不支持区间快速查找数据
 * 3. 跳表，支持区间查找 O(logn)
 * 
 * 跳表可以吗？可以解决问题，但是还有一种结构叫B+🌲
 * 通过二叉查找树演化而来
 * 怎么演化？
 * 1. 让二叉查找树支持按照区间来查找数据
 * 改造: 树中的节点并不存储数据本身，而是存储索引
 * 除此之外，我们把每个叶子节点串在一条链表上
 * 链表中的数据是从小到大有序的
 * 例如 6，10，15，23，27，33，42
 * 链表在最底下
 * 
 * 若占用过多内存，可以考虑💭一下磁盘
 * 通过🌲的高度即IO操作次数(尽量减少操作IO)
 * 那么如何降低树的高度(height)
 * 
 * 通过构建m叉树
 * 5叉树，16个数据，高度为2
 * 4叉树，16个数据，高度为3
 * 当m=100，1亿个数据，高度也只为3
 * 
 * 高度为3也只需要IO 3次
 * 
 * 因而查询的效率也高了
 * 
 * ***/

#include <iostream>
#include <vector>

using namespace std;

/***
 * B+ 树非叶子节点的定义
 * 假设keywords = [3,5,8,10]
 * 4个键值将数据分为5个区间:(通过将区间存在节点中)
 * (-INF,3),[3,5),[5,8),[8,10),[10,INF)
 * 5个区间分别对应: children[0]...children[4]
 * 
 * m值事先计算得到，计算的依据是让所有信息的大小正好等于页的大小
 * PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
 * 
 * ***/

struct bPlusTreeNode{
    static const int m = 5;
    int keywords[m-1];
    bPlusTreeNode *children[m];
};

/***
 * 这是B+树
 * B+树中的叶子节点跟内部节点不一样
 * 叶子节点存储的是值，而非区间
 * 每个叶子节点存储3个数据行的键值以及地址信息
 * 
 * k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小
 * PAGE_SIZE = k*4[keywords..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
 * 
 * ***/

struct bPlusTreeLeafNode{
    static const int k = 3;
    int keywords[k];
    long dataAddress[k];
    bPlusTreeLeafNode *prev;
    bPlusTreeLeafNode *next;
};

/***
 * 尽量让每个节点大小等于一个页的大小，读取一个节点只需要一次磁盘IO操作
 * ***/

/***
 * B+树的增删查改
 * 增，写入，分裂节点
 * 设置阈值
 * 删，删除小于m/2就合并节点
 * 
 * 其实跳表稍加改造也可以替换B+树
 * 作为数据库索引实现
 * 
 * B+树的特点
 * * 每个绩点中的字节点的个数不能超过m，也不能小于m/2
 * * 根节点的子节点个数可以不超过m/2，这是一个例外
 * * m叉树只存储索引，并不真正存储数据，这个有点类似跳表
 * * 通过链表将叶子节点串联在一起，方便按区间查找
 * * 一般情况下，根节点会被存储在内存中，其他节点存储在磁盘中
 * B-Tree 就是B树，翻译...
 * 
 * B是低级版的B+，B存数据，B树的字节点不少于m/2的m叉树
 * * ***/