首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >解析B+Tree索引在H2中的实现

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

原创
作者头像
用户5383110
发布2023-04-17 21:07:05
3180
发布2023-04-17 21:07:05
举报
文章被收录于专栏:DawnSqlDawnSql

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

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

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

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

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

2、数据 page 的定义

public abstract class Page implements Cloneable
{
   /**
     * Map this page belongs to
     */
    public MyMVMap<?, ?> map;

    /**
     * Position of this page's saved image within a Chunk or 0 if this page has not been saved yet.
     */
    public long pos;

    /**
     * The last result of a find operation is cached.
     */
    public int cachedCompare;

    /**
     * The estimated memory used in persistent case, IN_MEMORY marker value otherwise.
     */
    public int memory;

    /**
     * Amount of used disk space by this page only in persistent case.
     */
    public int diskSpaceUsed;

    /**
     * The keys.
     */
    public Object[] keys;

    /**
     * The storage for values.
     */
    public Object[] values;
   ...
}

3、叶子节点的定义

public static class Leaf extends Page
{
   ...
}

4、非叶子节点的定义

public static class NonLeaf extends Page
{
   ...
}

执行的过程

1、保存数据

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

2、相应代码

        String fileName = "/Users/chenfei/temp/my_store.db";
        FileUtils.delete(fileName);

        HashMap<String, Object> config = new HashMap<String, Object>();
        config.put("keysPerPage", 3);

        MVStore.Builder builder = new MVStore.Builder(config);
        builder.fileName(fileName);
        MVStore store = 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

            RootReference rootReference = flushAndGetRoot();
            RootReference lockedRootReference = null;
            if ((++attempt > 3 || rootReference.lockedForUpdate)) {
                lockedRootReference = lockRoot(rootReference, attempt);
                rootReference = lockedRootReference;
            }
            // 获取 root page
            Page rootPage = rootReference.root;

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

                // 向下遍历游标的位置
                CursorPos pos = traverseDown(rootPage, key);
                Page p = pos.page;
                int index = pos.index;
                tip = pos;
                pos = pos.parent;

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

p.insertLeaf(-index - 1, key, value);
int keyCount;
while ((keyCount = p.getKeyCount()) > store.getKeysPerPage()
        || p.getMemory() > store.getMaxPageSize()
        && keyCount > (p.isLeaf() ? 1 : 2)) {
long totalCount = p.getTotalCount();
int at = keyCount >> 1;
Object k = p.getKey(at);
Page split = p.split(at);
unsavedMemoryHolder.value += p.getMemory() + split.getMemory();
if (pos == null) {
        Object[] keys = { k };
        Page.PageReference[] children = {
                new Page.PageReference(p),
                new Page.PageReference(split)
        };
        p = Page.createNode(this, keys, children, totalCount, 0);
        break;
}
Page c = 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();
                    }
                }

4、主要过程的演示和详解

4.1、插入 key = 4, value = "my data 4" 后,root page 变成了一个叶子节点,keys 数组中包含了 4 ,values 数组中包含了 my data 4

4_btree
4_btree

调试结果

插入 key=4 时,root page 为空,root page 的 keys 也为空。因此将 4 直接插入 keys,将 my data 4 插入 values

4.2、插入 key = 7, value = "my data 7" 后,root page 变成为:

调试结果:

插入 key=7 时,首先通过 traverseDown(rootPage, key) 获取 page 和 page 中 keys 的 index,然后在 page 中插入相应的 keys 和 values。keys 数组必须保持有序

4.3、插入 key = 33, value = "my data 33" 后,root page 变成为:

调试结果

插入 key=33 时,首先通过 traverseDown(rootPage, key) 获取 page 和 page 中 keys 的 index,然后在 page 中插入相应的 keys 和 values。keys 数组必须保持有序

4.4、插入 key = 12, value = "my data 12" ,当 root page 插入 key = 12 时,因为 root page 节点已经超过了最大的 key 个数 (keysPerPage = 3), 那么它就会分裂成两个叶子节点,并且生成一个非叶子节点,将分裂的两个叶子节点,变成它的 children,同时让这个非叶子节点替换掉原来的节点

最终结果

调试结果

这里需求注意的一点是,父节点(非叶子节点)的 keys 数组,保存的值,是其从第二个子节点开始的 keys 数组的第一个值。

4.5、插入 key = 25, value = "my data 25"

调试结果

4.6、插入 key = 29, value = "my data 29"

调试结果

4.7、删除 key = 12, 首先从根节点开始向下遍历,获取 key=12 的 page 和 page 中的 index。如果该 page 的 keys 只有一个值,这删除它父节点 keys 对应的值,否则删除自己 keys 和 values 中的值

调试结果

4.8、删除 key = 25, 首先从根节点开始向下遍历,获取 key=25 的 page 和 page 中的 index。该 page 的 keys 只有一个值,因此只需要删除它父节点 keys 对应的值即可

调试结果

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • H2中的主键索引使用的是B+Tree
    • 1、在 h2 中节点分为叶子结点和非叶子节点
      • 2、数据 page 的定义
        • 3、叶子节点的定义
          • 4、非叶子节点的定义
          • 执行的过程
            • 1、保存数据
              • 2、相应代码
                • 3、保存的主要过程
                  • 3.1、获取 root page
                  • 3.2、根据输入的 key 通过 traverseDown 函数向下遍历 root page 找到,需要插入数据的 page 和 index.
                  • 3.3、插入数据后判断 page 中 keys 的数量是否大于最大每页中最大的限制数量,或者是 page 的大小大于最大的限制,如果是大于了,就要将 page 分裂成两个,并且新生成一个非叶子节点 (NonLeaf),将分裂的叶子节点放到新生成的非叶子节点下面。
                  • 3.4、更新 root page
                • 4、主要过程的演示和详解
                  • 4.1、插入 key = 4, value = "my data 4" 后,root page 变成了一个叶子节点,keys 数组中包含了 4 ,values 数组中包含了 my data 4
                  • 4.2、插入 key = 7, value = "my data 7" 后,root page 变成为:
                  • 4.3、插入 key = 33, value = "my data 33" 后,root page 变成为:
                  • 4.4、插入 key = 12, value = "my data 12" ,当 root page 插入 key = 12 时,因为 root page 节点已经超过了最大的 key 个数 (keysPerPage = 3), 那么它就会分裂成两个叶子节点,并且生成一个非叶子节点,将分裂的两个叶子节点,变成它的 children,同时让这个非叶子节点替换掉原来的节点
                  • 4.5、插入 key = 25, value = "my data 25"
                  • 4.6、插入 key = 29, value = "my data 29"
                  • 4.7、删除 key = 12, 首先从根节点开始向下遍历,获取 key=12 的 page 和 page 中的 index。如果该 page 的 keys 只有一个值,这删除它父节点 keys 对应的值,否则删除自己 keys 和 values 中的值
                  • 4.8、删除 key = 25, 首先从根节点开始向下遍历,获取 key=25 的 page 和 page 中的 index。该 page 的 keys 只有一个值,因此只需要删除它父节点 keys 对应的值即可
              相关产品与服务
              大数据处理套件 TBDS
              腾讯大数据处理套件(Tencent Big Data Suite,TBDS)依托腾讯多年海量数据处理经验,基于云原生技术和泛 Hadoop 生态开源技术对外提供的可靠、安全、易用的大数据处理平台。 TBDS可在公有云、私有云、非云化环境,根据不同数据处理需求组合合适的存算分析组件,包括 Hive、Spark、HBase、Flink、presto、Iceberg、Alluxio 等,以快速构建企业级数据湖、数据仓库。
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档