MIT6.5830 的数据库课程。Lab5 主要是完成 InnoDB 的索引，完成 B+ 树的查询、插入、删除操作。

索引

InnoDB存储数据

InnoDB是以数据页（默认16KB）为单位进行I/O读写的。

多个数据页之间是以双向链表结构连接（逻辑上的连续）的，数据页中的指针存在于File Header文件头。

数据页中的数据检索

数据页的作用是存储数据，重点就是User Records用户记录部分：数据页中的记录按照主键顺序组成单向链表。单向链表的特点是插入和删除非常方便，但是检索效率低——因此数据页中需要有一个页目录，起到快捷索引的功能。

上图要注意的细节：

每个分组最后一条记录的头信息中会存储该组一共有多少条记录，作为 n_owned 字段；
页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量被按照顺序存储为槽slot，每个槽相当于指针指向了不同组的最后一条记录；

通过页目录来索引记录时，由于页目录的槽是按顺序存储的，可以使用二分法快速定位要查询的记录在哪个槽的分组；再遍历槽所在分组的所有记录。

为什么槽slot存储的不是一个分组里的最小记录？

记录分组中记录的规定：

B+树的数据检索

在多个数据页之间，需要考虑如何建立索引才能方便的定位到指定的页，磁盘的I/O次数对索引的使用效率至关重要——InnoDB 采用了 B+ 树作为索引。

矮胖的 B+ 树需要的磁盘I/O次数更少

B+ 树（相对于B树）更加适合关键字的范围查找

B树和B+树的对比

B+ 树的每个节点都是一个数据页，通过上图可以看出B+树的特点：

只有叶子节点才存放数据，非叶子节点只存放目录项作为索引；
同层的节点按照索引键大小排序构成一个双向链表，便于范围查询。（依据什么）

B+树的增删查操作

B+树对于非叶子节点的子节点和索引的个数，定义方式可能会有不同，有的是说非叶子节点的子节点的个数为 M 阶，而索引的个数为 M-1（这个是维基百科里的定义），因此下面关于 B+树数据结构操作都是基于这个。但是在前面介绍 B+树时，说的是非叶子节点中有多少个子节点，就有多少个索引 ，主要是 MySQL 用到的 B+树就是这个特性。

mysql中用到的B+树（非叶子节点子节点个数=索引个数）

单点查询

因为B树的每个节点既存索引又存记录，所以相较于B+树平均时间复杂度更低。但是在相同的数据量情况下，B+树的非叶子节点可以存储更多的索引，所以B+树更加矮胖，查询底层节点所需的磁盘I/O更小。

插入操作

非叶子节点的索引也会同时存在在子节点中，并且是在子节点中所有索引的最大或最小。

若为空树，创建一个叶子结点，然后将记录插入其中，此时这个叶子结点也是根结点，插入操作结束。
针对叶子类型结点：根据key值找到叶子结点，向这个叶子结点插入记录。插入后，若当前结点key的个数小于等于 m-1，则插入结束。否则将这个叶子结点分裂成左右两个叶子结点，左叶子结点包含前 m/2 个记录，右结点包含剩下的记录，将第 m/2+1 个记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针向左结点，右孩子指针向右结点。将当前结点的指针指向父结点，然后执行第3步。
针对索引类型结点：若当前结点key的个数小于等于m-1，则插入结束。否则，将这个索引类型结点分裂成两个索引结点，左索引结点包含前 (m-1)/2 个key，右结点包含后 m-(m-1)/2 的个key，将第 m/2 个key进位到父结点中，进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点，然后重复第3步。

例如5阶B+树的节点2 ≤ key的数量 ≤ 4

删除操作

删除叶子结点中对应的key，删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1，删除操作结束，否则执行第二步。
若兄弟节点的key有富余，向兄弟节点借一个记录，同时用借到的key替换父节点中的key。
若兄弟节点中没有富余的key，则当前节点和兄弟节点合并为一个新的叶子节点，并删除父节点中key（父节点中的这个key两边的孩子指针就变成了一个指针）。
若索引类型节点的key个数大于等于Math.ceil(m-1)/2 – 1，删除操作结束，否则执行第五步。
若兄弟节点有富余，父节点key下移，兄弟节点key上移，删除结束。
若兄弟节点也没有富余，则当前节点和兄弟节点以及父节点的下移key合并为一个新节点。

删除22：

删除15：

删除7：

范围查询

B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助。而 B 树没有将所有的叶子节点用链表串联起来的结构，因此只能通过树的遍历来完成范围查询，涉及到更多节点的磁盘I/O，范围查询效率远不如B+树。

InnoDB选用 B+ 树的原因（前面也反复提及）

B+ 树的磁盘读写I/O代价更低
B+ 树的查询效率更加稳定
B+ 树便于范围查询（数据库查询的常态）

Exercise 1

实现findLeafPage()方法，递归返回需要的叶子节点。

lab中给出的outline:

给定值1，此函数应返回第一个叶页。同样，给定值8，该函数应返回第二页。而在某种case下，如果给我们一个键值6。可能有重复的键，所以两个叶页上可能都有6。在这种情况下，函数应该返回第一个（左）叶页。
递归的搜索页面，直到搜索到所需的叶子节点页面。如果 BTreePageId.LEAF 则表明这是叶子页面退出递归，否则则是内部页面，需要遍历内部页面中的entrys，并与每个key值做比较，递归进入到下一层的节点。

private BTreeLeafPage findLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreePageId pid, Permissions perm,
                                   Field f)
        throws DbException, TransactionAbortedException {
    // TODO: some code goes here
    // 共有四种节点类型: ROOT_PTR、INTERNAL、LEAF、HEADER
    int type = pid.pgcateg();  // 返回这个页面的类别
    // 叶子节点直接返回该节点的pid页面，同时也是递归结束的条件
    if (type == BTreePageId.LEAF) {
        return (BTreeLeafPage) getPage(tid, dirtypages, pid, perm);
    }
    // 非叶子节点直接使用READ权限遍历entries
    BTreeInternalPage internalPage = (BTreeInternalPage) getPage(tid, dirtypages, pid, Permissions.READ_ONLY);
    Iterator<BTreeEntry> it = internalPage.iterator();
    BTreeEntry entry = null;
    while (it.hasNext()) {
        entry = it.next();
        // 如果f为空，递归查找左子节点
        if (f == null) {
            return findLeafPage(tid, dirtypages, entry.getLeftChild(), perm, f);
        }
        if (entry.getKey().compare(Op.GREATER_THAN_OR_EQ, f)) {
            return findLeafPage(tid, dirtypages, entry.getLeftChild(), perm, f);
        }
    }
    // 最后一层节点为叶子节点，且内部节点的entry不应该为空
    assert entry != null;
    return findLeafPage(tid, dirtypages, entry.getRightChild(), perm, f);
}

Exercise 2

完成B+树的插入操作，实现splitLeafPage()方法和splitInternalPage()方法。

Exercise1中的任务可以查找我们应该插入元组的正确叶页，但是每个页面的插槽数量有限，尝试将元组插入已满的叶页会导致该页面分裂，以便元组在均匀分布在两个页面当中。

叶节点的分裂需要复制一份数据的备份到父节点。而内部节点不需要刻意维护数据在底层，所以其分裂的key是被挤到父节点的。
叶子节点的分裂还需要维护两个节点之间的指针指向。

splitLeafPage()：当叶子节点中的元组数量等于N时，将其拆分为两个叶节点，并返回插入tuple所在的page。

lab中的outline提示

public BTreeLeafPage splitLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreeLeafPage page, Field field)
        throws DbException, IOException, TransactionAbortedException {
    // TODO: some code goes here
    // 1、先处理子节点
    // 创建一个右叶子结点，并进行均匀分配
    BTreeLeafPage newRightPage = (BTreeLeafPage) getEmptyPage(tid, dirtypages, BTreePageId.LEAF);
    int numTuples = page.getNumTuples();
    Iterator<Tuple> reverseIt = page.reverseIterator();
    for (int i = 0; i < numTuples / 2; i++) {
        Tuple tuple = reverseIt.next();
        page.deleteTuple(tuple);
        newRightPage.insertTuple(tuple);
    }
    // leftNode <=> page <=> rightNode 需要变成 leftNode <=> (page <=> newRightPage) <=> rightNode
    BTreePageId rightSiblingId = page.getRightSiblingId();  // 获取该页右侧同级的id
    BTreeLeafPage rightNode = rightSiblingId == null ? null : (BTreeLeafPage) getPage(tid, dirtypages, rightSiblingId, Permissions.READ_ONLY);
    if (rightNode != null) {
        rightNode.setLeftSiblingId(newRightPage.getId());
        newRightPage.setRightSiblingId(rightNode.getId());
        dirtypages.put(rightNode.getId(), rightNode);
    }
    page.setRightSiblingId(newRightPage.getId());
    newRightPage.setLeftSiblingId(page.getId());
    dirtypages.put(newRightPage.getId(), newRightPage);
    dirtypages.put(page.getId(), page);

    // 2、再处理父节点
    // "复制"中间节点并插入父节点中，并设置指针
    Field midKey = newRightPage.iterator().next().getField(keyField);
    BTreeEntry insertEntry = new BTreeEntry(midKey, page.getId(), newRightPage.getId());
    // 获取具有读写权限的父页面，如果父节点中key的数量到达了n-1，则会调用splitInternalPage()方法继续递归，最终返回一个可以插入新key的内部节点页面
    BTreeInternalPage parentPage = getParentWithEmptySlots(tid, dirtypages, page.getParentId(), field);
    parentPage.insertEntry(insertEntry);
    dirtypages.put(parentPage.getId(), parentPage);
    updateParentPointers(tid, dirtypages, parentPage);  // 设置指针指向

    // 返回应该插入新元组的叶页
    if (field.compare(Op.GREATER_THAN_OR_EQ, midKey)) {
        return newRightPage;
    } else {
        return page;
    }
}

splitInternalPage()：当内部节点中的元组数量等于N时，将其拆分为两个内部节点

public BTreeInternalPage splitInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
                                           BTreeInternalPage page, Field field)
        throws DbException, IOException, TransactionAbortedException {
    // TODO: some code goes here
    // 创建一个内部节点，并进行均匀分配
    BTreeInternalPage newRightPage = (BTreeInternalPage) getEmptyPage(tid, dirtypages, BTreePageId.INTERNAL);
    int numEntries = page.getNumEntries();
    Iterator<BTreeEntry> reverseIt = page.reverseIterator();
    for (int i = 0; i < numEntries / 2; i++) {
        // 与分裂叶子节点不同的是内部节点的单位是Entries，用于唯一标示的则是entry中的RecordId，而插入操作则会改变RecordId
        // 因此需要先删除后插入
        BTreeEntry entry = reverseIt.next();
        // 删除哪个child
        page.deleteKeyAndRightChild(entry);
        newRightPage.insertEntry(entry);
    }

    // 将子节点"挤到"父节点中，并设置指针指向
    BTreeEntry midEntry = reverseIt.next();
    page.deleteKeyAndRightChild(midEntry);
    midEntry.setLeftChild(page.getId());
    midEntry.setRightChild(newRightPage.getId());
    BTreeInternalPage parent = getParentWithEmptySlots(tid, dirtypages, page.getParentId(), midEntry.getKey());
    parent.insertEntry(midEntry);
    updateParentPointers(tid, dirtypages, page);
    updateParentPointers(tid, dirtypages, newRightPage);
    updateParentPointers(tid, dirtypages, parent);

    // 更新脏页并返回
    dirtypages.put(page.getId(), page);
    dirtypages.put(parent.getId(), parent);
    dirtypages.put(newRightPage.getId(), newRightPage);

    if (field.compare(Op.GREATER_THAN_OR_EQ, midEntry.getKey())) {
        return newRightPage;
    } else {
        return page;
    }
}

Exercise 3

完成B+树的删除操作中的节点key重分配，实现stealFromLeafPage()方法和stealFromLeftInternalPage()、stealFromRightInternalPage()方法。

在 B+ 树的删除中，当节点中的 key 个数小于最小限制后，会进行节点之间的合并，合并中当兄弟节点有富余的 key 时会在两节点之间形成 key 的重分配。

stealFromLeafPage()：

public void stealFromLeafPage(BTreeLeafPage page, BTreeLeafPage sibling,
                              BTreeInternalPage parent, BTreeEntry entry, boolean isRightSibling) throws DbException {
    // TODO: some code goes here
    Iterator<Tuple> siblingIt = isRightSibling ? sibling.iterator() : sibling.reverseIterator();
    int sourceNumTuples = page.getNumTuples();
    int siblingTuplesNum = sibling.getNumTuples();
    int midTuplesNum = (sourceNumTuples + siblingTuplesNum) / 2;
    while (sourceNumTuples < midTuplesNum) {
        // 保证B+树节点的平衡性
        Tuple siblingTuple = siblingIt.next();
        sibling.deleteTuple(siblingTuple);
        page.insertTuple(siblingTuple);
        sourceNumTuples++;
    }
    // 更新父节点中的key
    Tuple headSibling = siblingIt.next();
    entry.setKey(headSibling.getField(keyField));
    parent.updateEntry(entry);
}

stealFromLeftInternalPage()：

public void stealFromLeftInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
                                      BTreeInternalPage page, BTreeInternalPage leftSibling, BTreeInternalPage parent,
                                      BTreeEntry parentEntry) throws DbException, TransactionAbortedException {
    // TODO: some code goes here
    // 先将父节点的key移动到下层内部节点中
    Iterator<BTreeEntry> leftIt = leftSibling.reverseIterator();
    BTreeEntry itEntry = leftIt.next();
    BTreeEntry oldParent = new BTreeEntry(parentEntry.getKey(), itEntry.getRightChild(), page.iterator().next().getLeftChild());
    page.insertEntry(oldParent);

    // 保证B+树平衡性，进行均匀分配
    int sourceEntriesNum = page.getNumEntries();
    int siblingEntriesNum = leftSibling.getNumEntries();
    int midEntriesNum = (sourceEntriesNum + siblingEntriesNum) / 2;
    while (sourceEntriesNum < midEntriesNum) {
        leftSibling.deleteKeyAndRightChild(itEntry);
        page.insertEntry(itEntry);
        itEntry = leftIt.next();
        sourceEntriesNum++;
    }

    // 新的父节点被旋转上去则不需担心子节点指向
    BTreeEntry newParent = itEntry;
    leftSibling.deleteKeyAndRightChild(newParent);
    parentEntry.setKey(newParent.getKey());
    parent.updateEntry(parentEntry);

    // 设置脏页
    dirtypages.put(page.getId(), page);
    dirtypages.put(leftSibling.getId(), leftSibling);
    dirtypages.put(parent.getId(), parent);
    updateParentPointers(tid, dirtypages, page);
}

stealFromRightInternalPage()：

public void stealFromRightInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
                                       BTreeInternalPage page, BTreeInternalPage rightSibling, BTreeInternalPage parent,
                                       BTreeEntry parentEntry) throws DbException, TransactionAbortedException {
    // TODO: some code goes here
    // 先将父节点的key移动到下层内部节点中
    Iterator<BTreeEntry> rightIt = rightSibling.iterator();
    BTreeEntry itEntry = rightIt.next();
    BTreeEntry oldParent = new BTreeEntry(parentEntry.getKey(), page.reverseIterator().next().getRightChild(), itEntry.getLeftChild());
    page.insertEntry(oldParent);

    int sourceEntriesNum = page.getNumEntries();
    int siblingEntriesNum = rightSibling.getNumEntries();
    int midEntriesNum = (sourceEntriesNum + siblingEntriesNum) / 2;
    // 保证B+树平衡性，进行均匀分配
    while (sourceEntriesNum < midEntriesNum) {
        rightSibling.deleteKeyAndLeftChild(itEntry);
        page.insertEntry(itEntry);
        itEntry = rightIt.next();
        sourceEntriesNum++;
    }
    // 新的父节点被旋转上去
    BTreeEntry newParent = itEntry;
    rightSibling.deleteKeyAndLeftChild(newParent);
    parentEntry.setKey(newParent.getKey());
    parent.updateEntry(parentEntry);
    // 设置脏页
    dirtypages.put(page.getId(), page);
    dirtypages.put(rightSibling.getId(), rightSibling);
    dirtypages.put(parent.getId(), parent);
    updateParentPointers(tid, dirtypages, page);
}

Exercise 4

完成B+树的删除操作中的合并操作，实现mergeLeafPages()方法和mergeInternalPages()方法。

在删除中当兄弟节点没有key富余时，需要将该节点与兄弟节点合并，叶子节点和内部节点的合并策略不同之处在于叶子节点删除上层key，内部节点将上层key移到下面一齐合并。

mergeLeafPages()：

public void mergeLeafPages(TransactionId tid, Map<PageId, Page> dirtypages,
                           BTreeLeafPage leftPage, BTreeLeafPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
        throws DbException, IOException, TransactionAbortedException {

    // TODO: some code goes here
    Iterator<Tuple> rightIt = rightPage.iterator();
    // 将右节点的key全部移动到左节点中进行节点合并
    while (rightIt.hasNext()) {
        Tuple next = rightIt.next();
        rightPage.deleteTuple(next);
        leftPage.insertTuple(next);
    }

    // 设置叶子节点之间的指针指向
    BTreePageId newRightNode = rightPage.getRightSiblingId();
    if (newRightNode == null) {
        leftPage.setRightSiblingId(null);
    } else {
        leftPage.setRightSiblingId(newRightNode);
        BTreeLeafPage newRightPage = (BTreeLeafPage) getPage(tid, dirtypages, newRightNode, Permissions.READ_WRITE);
        newRightPage.setLeftSiblingId(leftPage.getId());
    }
    // 删除父节点中的key
    setEmptyPage(tid, dirtypages, rightPage.getId().getPageNumber());
    deleteParentEntry(tid, dirtypages, leftPage, parent, parentEntry);
    dirtypages.put(leftPage.getId(), leftPage);
    dirtypages.put(parent.getId(), parent);
}

mergeInternalPages()：

public void mergeInternalPages(TransactionId tid, Map<PageId, Page> dirtypages,
                               BTreeInternalPage leftPage, BTreeInternalPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
        throws DbException, IOException, TransactionAbortedException {

    // TODO: some code goes here
    Iterator<BTreeEntry> rightIt = rightPage.iterator();

    // 与叶子节点的区别 -- 需要将父亲节点拉下来
    BTreeEntry pullNode = new BTreeEntry(parentEntry.getKey(), leftPage.reverseIterator().next().getRightChild(),
            rightPage.iterator().next().getLeftChild());
    leftPage.insertEntry(pullNode);
    // 将右节点的key全部移动到左节点中进行节点合并
    while (rightIt.hasNext()) {
        BTreeEntry next = rightIt.next();
        rightPage.deleteKeyAndRightChild(next);
        leftPage.insertEntry(next);
    }
    // 更新父节点指针
    updateParentPointers(tid, dirtypages, leftPage);
    // 删除父节点中的key
    setEmptyPage(tid, dirtypages, rightPage.getId().getPageNumber());
    deleteParentEntry(tid, dirtypages, leftPage, parent, parentEntry);
    dirtypages.put(leftPage.getId(), leftPage);
    dirtypages.put(parent.getId(), parent);
}