H2 Database MvMap 插入数据流程

H2Database 使用 MVStore 作为默认的存储子系统，支持多版本，持久化的键值存储。
其中每一个 MVMap 对象代表了一颗 btree。
MVMap 里包含了 btree 根页面的引用，这颗 btree 可以表示一张表、一个索引，或者用来记录 undo log 等。

使用

1
2
3
4
5
6
7
8
// 1.根据数据库文件名称打开 mvStore
MVStore s = MVStore.open(fileName);
// 2.指定名称创建 mvMap
MVMap<Integer, String> map = s.openMap("data");
// 3.将数据插入到 mvMap 上
for (int i = 0; i < 400; i++) {
    map.put(i, "Hello-" + i);
}

相关类

MVMap 类

成员变量

包含了 MVMap 这个 btree 的唯一 id，btree 的根节点引用。btree 每个节点上存储的 key、value 类型。
以及 keysBuffer 和 valuesBuffer 用于追加写，最后再应用到 btree 上。

1
2
3
4
5
6
7
8
9
10
11
12
// 关联的 mvStore
public final MVStore store;
// 指向当前 root page
private final AtomicReference<RootReference<K,V>> root;
private final int id; // 当前 mvMap 的唯一 id
private final long createVersion;
private final DataType<K> keyType; // 存储的 key 类型
private final DataType<V> valueType; // 存储的 value 类型
private final int keysPerPage; // 每个 page 存储的 key 数量,默认48
private final boolean singleWriter; // 只有开启了 singleWriter 参数,才会先写缓冲区(追加写).不开启的话都是直接写到 btree 上
private final K[] keysBuffer; // key 缓冲,最终会写到 btree 上
private final V[] valuesBuffer; // value 缓冲,最终会写到 btree 上

Page 类

一个 Page 对象表示了 btree 上的一个节点。
Page 按照类型分为叶子节点和非叶子节点，分别使用 Leaf 和 NonLeaf 表示。
其中叶子节点含有 key-value 键值对，非叶子结点只含有键(keys)还有指向叶子结点的指针。

继承体系

1
2
3
4
5
6
7
8
9
10
11
12
Page
    代表 btree 中的一个节点
    Leaf
        叶子节点
    NonLeaf
        非叶子节点
DataType 数据类型
    BasicDataType
        LongDataType
        StringDataType
        VersionedValueType
            版本化值的值类型

常用方法

1
2
3
4
5
6
7
8
9
10
11
// 将 key, value 保存到 keysBuffer 和 valuesBuffer 里,超出阈值则追加到 mvMap 上。
flushAppendBuffer()

// 根据 key 获取 value
get()

// 当前页大小超出阈值，页分裂
split()

// 操作 btree。添加、替换或删除键值对
operate()

作用

插入 key, value 到 mvMap 上的指定位置。

流程

主要逻辑在 MVMap#operate 里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1.获取 mvMap 根节点引用，获取对应的根节点 root page
2.从根节点开始二分遍历，根据 key 遍历 btree,找到 key 所在的位置 pos
    CursorPos.traverseDown(rootPage, key)
3.获取操作(插入/删除..)位置对应的 pos 的相关信息
    获取 page: 当前 key 对应的 btree 节点
    获取 index: 当前 key 对应的在 page 上的下标
4.根据 index 获取 page 上的当前值(如果是插入操作当前值为 null)
5.根据 当前值、目标值 和 游标位置 决定操作类型(比如 put 操作)
6.具体 mvMap 操作
    6.1.remove 操作
    6.2.put 操作
        6.2.1.获取当前值(如果是事务commit操作,此处会获取 VersionedValueUncommitted 里的 defaultRow)
        6.2.2.copy page
        根据 index 是负数决定执行插入 or 更新操作
        6.2.3.如果执行插入操作
            6.2.3.1.插入 key, value 到叶子节点的指定 index
            6.2.3.2.page 分裂操作,触发条件: key 数量超过每页最大键数量限制(默认48) 或 page内存超过最大page大小
                6.2.3.2.1.计算 page 分裂位置(中间位置)
                6.2.3.2.2.获取 page 中间位置的 key
                6.2.3.2.3.分裂 page.执行完毕后 split 为分裂后的第二个页面, p 为分裂后的第一个页面
                6.2.3.2.4.记录需要保存的内存
                6.2.3.2.5.如果当前节点为根节点,则创建一个新的节点作为根节点
                    创建 key 存储空间(1)
                    插入 key
                    创建 children 存储空间(2)
                    插入孩子节点0 page
                    插入孩子节点1 split
                    创建非叶子节点作为 root 节点, 传入孩子节点信息
        6.2.4.如果执行更新操作,直接设置 page 指定下标对应的值
7.替换 root page (pos 为父节点的 pos)
    原子更新 root page 引用

MVMap#operate

org.h2.mvstore.MVMap#operate 相关代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/** 添加、替换 或 删除 mvMap 上的键值对
 * Add, replace or remove a key-value pair.
 *
 * @param key the key (may not be null)
 * @param value new value, it may be null when removal is intended 新值，当打算删除时它可能为空
 * @param decisionMaker command object to make choices during transaction.
 * @return previous value, if mapping for that key existed, or null otherwise
 */
public V operate(K key, V value, DecisionMaker<? super V> decisionMaker) {
    IntValueHolder unsavedMemoryHolder = new IntValueHolder();
    int attempt = 0;
    while(true) {
        RootReference<K,V> rootReference = flushAndGetRoot(); // 1.获取 mvMap 根节点引用
        boolean locked = rootReference.isLockedByCurrentThread(); // 2.1.判断当前线程是否已经锁定了根节点
        if (!locked) { // 2.2.如果当前线程没有锁定根节点，则尝试加锁
            if (attempt++ == 0) {
                beforeWrite();
            }
            if (attempt > 3 || rootReference.isLocked()) {
                rootReference = lockRoot(rootReference, attempt);
                locked = true;
            }
        }
        Page<K,V> rootPage = rootReference.root; // 3.获取根节点 root page
        long version = rootReference.version; // 写版本号
        CursorPos<K,V> tip;
        V result;
        unsavedMemoryHolder.value = 0;
        try {
            CursorPos<K,V> pos = CursorPos.traverseDown(rootPage, key); // 2.从根节点开始，根据 key 遍历 btree,找到 key 的位置 pos
            if (!locked && rootReference != getRoot()) {
                continue;
            }
            Page<K,V> p = pos.page; // 3.获取操作(插入/删除..)位置对应的 pos 对应的 page
            int index = pos.index; // 获取当前 key 对应的在 page 上的下标
            tip = pos;
            pos = pos.parent; // 注意：这里需要获取当前 post 对应的父节点 pos(根节点的 parent pos 为 null)，因为后面需要根据父节点来更新 root page
            result = index < 0 ? null : p.getValue(index); // 4.根据 index 获取 page 上的当前值(如果是插入操作当前值为 null)
            Decision decision = decisionMaker.decide(result, value, tip); // 5.根据 当前值、目标值 和 游标位置 决定操作类型

            switch (decision) { // 6.具体 mvMap 操作
                case REPEAT:
                    decisionMaker.reset();
                    continue;
                case ABORT:
                    if (!locked && rootReference != getRoot()) {
                        decisionMaker.reset();
                        continue;
                    }
                    return result;
                case REMOVE: { // 6.1.remove 操作
                    if (index < 0) {
                        if (!locked && rootReference != getRoot()) {
                            decisionMaker.reset();
                            continue;
                        }
                        return null;
                    }

                    if (p.getTotalCount() == 1 && pos != null) { // 如果当前页只有一个键且有父节点，则尝试移除父节点的键
                        int keyCount;
                        do {
                            p = pos.page;
                            index = pos.index;
                            pos = pos.parent;
                            keyCount = p.getKeyCount();
                            // condition below should always be false, but older
                            // versions (up to 1.4.197) may create
                            // single-childed (with no keys) internal nodes,
                            // which we skip here
                        } while (keyCount == 0 && pos != null);

                        if (keyCount <= 1) {
                            if (keyCount == 1) { // 如果父节点只有一个键，替换父节点为叶子节点
                                assert index <= 1;
                                p = p.getChildPage(1 - index);
                            } else {
                                // if root happens to be such single-childed
                                // (with no keys) internal node, then just
                                // replace it with empty leaf
                                p = Page.createEmptyLeaf(this);
                            }
                            break;
                        }
                    }
                    p = p.copy(); // 复制页面并移除键
                    p.remove(index); // 删除 page 指定 index 的值
                    break;
                }
                case PUT: { // 6.2.put 操作
                    value = decisionMaker.selectValue(result, value); // 6.2.1.获取当前值(如果是事务commit操作,此处会获取 VersionedValueUncommitted 里的 defaultRow)
                    p = p.copy(); // 6.2.2.copy page
                    if (index < 0) { // 6.2.3.插入操作
                        p.insertLeaf(-index - 1, key, value); // 6.2.3.1.插入叶子节点
                        int keyCount;
                        while ((keyCount = p.getKeyCount()) > store.getKeysPerPage()
                                || p.getMemory() > store.getMaxPageSize()
                                && keyCount > (p.isLeaf() ? 1 : 2)) { // 6.2.3.2.page 分裂: key数量超过每页最大键数量限制(默认48) 或 page内存超过最大page大小
                            long totalCount = p.getTotalCount();
                            int at = keyCount >> 1; // 6.2.3.2.1.计算 page 分裂位置(中间位置)
                            K k = p.getKey(at); // 6.2.3.2.2.获取 page 中间位置的 key
                            Page<K,V> split = p.split(at); // 6.2.3.2.3.分裂 page.执行完毕后 split 为分裂后的第二个页面, p 为分裂后的第一个页面
                            unsavedMemoryHolder.value += p.getMemory() + split.getMemory(); // 6.2.3.2.4.记录需要保存的内存
                            if (pos == null) { // 6.2.3.2.5.如果当前节点为根节点,则创建一个内部节点作为根节点
                                K[] keys = p.createKeyStorage(1); // 创建 key 存储空间(1)
                                keys[0] = k; // 插入 key
                                Page.PageReference<K,V>[] children = Page.createRefStorage(2); // 创建 children 存储空间(2)
                                children[0] = new Page.PageReference<>(p); // 插入孩子节点0 page
                                children[1] = new Page.PageReference<>(split); // 插入孩子节点1 split
                                p = Page.createNode(this, keys, children, totalCount, 0); // 创建非叶子节点作为 root 节点, 传入孩子节点信息
                                break;
                            }
                            Page<K,V> c = p;
                            p = pos.page;
                            index = pos.index;
                            pos = pos.parent;
                            p = p.copy();
                            p.setChild(index, split);
                            p.insertNode(index, k, c);
                        }
                    } else {
                        p.setValue(index, value); // 6.2.4.更新操作,直接设置 page 指定下标对应的值
                    }
                    break;
                }
            }
            rootPage = replacePage(pos, p, unsavedMemoryHolder); // 7.替换 root page (pos 为父节点的 pos)
            if (!locked) { // 未上锁
                rootReference = rootReference.updateRootPage(rootPage, attempt); // 更新 root page 引用
                if (rootReference == null) { // 没有更新成功
                    decisionMaker.reset(); // 重试
                    continue; // continue 重试插入
                }
            }
            if (isPersistent()) {
                registerUnsavedMemory(unsavedMemoryHolder.value + tip.processRemovalInfo(version));
            }
            return result;
        } finally {
            if(locked) {
                unlockRoot(rootPage);
            }
        }
    }
}

页分裂

默认 Page 大小为 48 (KeysPerPage = 48)，所以当顺序插入第 49 个 key-value 时，会发生第一次页分裂。
第一次分裂后的结构示例：

1
2
3
4
5
6
7
8
9
NonLeaf
    keys: [24]
    children:
        - Leaf_0
            keys: [0..23]
            values: ['Hello-0', ... , 'Hello-23']
        - Leaf_1
            keys: [24..48]
            values: ['Hello-24', ... , 'Hello-48']

类