解析B+Tree索引在H2中的实现

2023-04-17 163

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

全局流量管理 GTM，标准版 1个月

公共DNS（含HTTPDNS解析），每月1000万次HTTP解析

云解析 DNS，旗舰版 1个月

简介： 提到数据库索引的时候，一般都会提到 B+Tree，因为主流数据库都使用它。我们的DawnSql使用的是 H2 中的存储引擎，因此也是使用 B+Tree。这篇文章的目的是帮助读者更快的掌握 B+Tree 在存储引擎中的作用，以及具体的实现。

提到数据库索引的时候，一般都会提到 B+Tree，因为主流数据库都使用它。我们的DawnSql使用的是 H2 中的存储引擎，因此也是使用 B+Tree。这篇文章的目的是帮助读者更快的掌握 B+Tree 在存储引擎中的作用，以及具体的实现。

H2中的主键索引使用的是B+Tree

1、在 h2 中节点分为叶子结点和非叶子节点

叶子节点：包含数据和索引 (values 和 keys)

非叶子节点：只包含索引 (keys)

2、数据 page 的定义

publicabstractclassPageimplementsCloneable{
/*** Map this page belongs to*/publicMyMVMap<?, ?>map;
/*** Position of this page's saved image within a Chunk or 0 if this page has not been saved yet.*/publiclongpos;
/*** The last result of a find operation is cached.*/publicintcachedCompare;
/*** The estimated memory used in persistent case, IN_MEMORY marker value otherwise.*/publicintmemory;
/*** Amount of used disk space by this page only in persistent case.*/publicintdiskSpaceUsed;
/*** The keys.*/publicObject[] keys;
/*** The storage for values.*/publicObject[] values;
   ...
}

复制

3、叶子节点的定义

publicstaticclassLeafextendsPage{
   ...
}

复制

4、非叶子节点的定义

publicstaticclassNonLeafextendsPage{
   ...
}

复制

执行的过程

1、保存数据

例如：要保存数据，"my data 4", "my data 7"。设置它们的索引为: 4， 7

2、相应代码

StringfileName="/Users/chenfei/temp/my_store.db";
FileUtils.delete(fileName);
HashMap<String, Object>config=newHashMap<String, Object>();
config.put("keysPerPage", 3);
MVStore.Builderbuilder=newMVStore.Builder(config);
builder.fileName(fileName);
MVStorestore=builder.open();
/*** 初始化一个 MVMap 对象，相当于创建了一个空的表，表的主键是 Integer 类型的，数据是字符串类型的* 在用 Create table 语句创建表时，数据是 Object[] 类型的，表示一行的数据。* 在初始时会创建一个空的 page 成为 root page，可以通过 getRootPage() 方法获取这个 root page* 例如：Page rootPage = m.getRootPage();* */MVMap<Integer, String>m=store.openMap("cache_data");
/*** 保存 key = 4, value = "my data 4" 的值* */m.put(4, "my data 4");
/*** 保存 key = 7, value = "my data 7" 的值* */m.put(7, "my data 7");

复制

3、保存的主要过程

3.1、获取 root page

RootReferencerootReference=flushAndGetRoot();
RootReferencelockedRootReference=null;
if ((++attempt>3||rootReference.lockedForUpdate)) {
lockedRootReference=lockRoot(rootReference, attempt);
rootReference=lockedRootReference;
            }
// 获取 root pagePagerootPage=rootReference.root;

复制

3.2、根据输入的 key 通过 traverseDown 函数向下遍历 root page 找到，需要插入数据的 page 和 index.

// 向下遍历游标的位置CursorPospos=traverseDown(rootPage, key);
Pagep=pos.page;
intindex=pos.index;
tip=pos;
pos=pos.parent;

复制

3.3、插入数据后判断 page 中 keys 的数量是否大于最大每页中最大的限制数量，或者是 page 的大小大于最大的限制，如果是大于了，就要将 page 分裂成两个，并且新生成一个非叶子节点 (NonLeaf)，将分裂的叶子节点放到新生成的非叶子节点下面。

p.insertLeaf(-index-1, key, value);
intkeyCount;
while ((keyCount=p.getKeyCount()) >store.getKeysPerPage()
||p.getMemory() >store.getMaxPageSize()
&&keyCount> (p.isLeaf() ?1 : 2)) {
longtotalCount=p.getTotalCount();
intat=keyCount>>1;
Objectk=p.getKey(at);
Pagesplit=p.split(at);
unsavedMemoryHolder.value+=p.getMemory() +split.getMemory();
if (pos==null) {
Object[] keys= { k };
Page.PageReference[] children= {
newPage.PageReference(p),
newPage.PageReference(split)
        };
p=Page.createNode(this, keys, children, totalCount, 0);
break;
}
Pagec=p;
p=pos.page;
index=pos.index;
pos=pos.parent;
p=p.copy();
p.setChild(index, split);
p.insertNode(index, k, c);
}

复制

3.4、更新 root page

rootPage=replacePage(pos, p, unsavedMemoryHolder);
if (lockedRootReference==null) {
if (!updateRoot(rootReference, rootPage, attempt)) {
decisionMaker.reset();
continue;
                    } else {
notifyWaiters();
                    }
                }