提到数据库索引的时候，一般都会提到 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(); } }
复制
4、主要过程的演示和详解
4.1、插入 key = 4, value = "my data 4" 后，root page 变成了一个叶子节点，keys 数组中包含了 4 ，values 数组中包含了 my data 4
调试结果
插入 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 对应的值即可
调试结果
