H2 Database MvMap 插入数据流程

使用

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);
}

作用

插入 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']

类