数据库原理与设计

1、分析B+树、LSM树作为存储引擎数据结构的特点

B+树：

  • 每个节点中的元素从小到大排列
  • 对于每个非叶子结点，其左子树中的所有key都小于它，右子树中的key都大于等于它
  • 所有的叶子结点都位于同一层
  • 非叶子节点只存储key和指针
  • 叶子节点存储data（带顺序访问的B+树还会存储一个指向相邻叶子节点的指针）
  • 一个节点的大小为一页

LSM树：

  • 由两个或以上的存储结构组成
  • 是一个多层结构，上小下大
  • 每一层都是有序的
  • 第一层在内存中，其他层在磁盘中

2、分别写出读请求（点查）和写请求（插入）访问上述对应数据结构时的访问流程

B+树：

  • 读请求
    1. 访问根节点，二分查找
    2. 访问相应的子树，二分查找
    3. 重复步骤2，直到查询到对应的data
    4. 如果是聚集索引则结束；如果非聚集索引，则把得到的data当成key去聚集索引里查找data
  • 写请求
    1. 若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。
    2. 针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录。插入后，若当前结点key的个数小于等于m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前m/2个记录，右结点包含剩下的记录，将第m/2+1个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。
    3. 针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前(m-1)/2个key，右结点包含m-(m-1)/2个key，将第m/2个key进位到父结点中，进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

LSM树：

  • 读请求
    1. 在内存中查找（C0）
    2. 若未命中，则依次往下层查找
    3. 重复2步骤，直至找到
  • 写请求
    1. 日志先行，既先插入操作日志
    2. 随后将新纪录的索引插入到C0（内存中）
    3. 当C0达到一定的阙值，数据顺序刷到C1并与之合并，以此类推