提到数据库索引的时候,一般都会提到 B+Tree,因为主流数据库都使用它。我们的DawnSql使用的是 H2 中的存储引擎,因此也是使用 B+Tree。这篇文章的目的是帮助读者更快的掌握 B+Tree 在存储引擎中的作用,以及具体的实现。
叶子节点:包含数据和索引 (values 和 keys)
非叶子节点:只包含索引 (keys)
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;
...
}
public static class Leaf extends Page
{
...
}
public static class NonLeaf extends Page
{
...
}
例如:要保存数据,"my data 4", "my data 7"。设置它们的索引为: 4, 7
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");
RootReference rootReference = flushAndGetRoot();
RootReference lockedRootReference = null;
if ((++attempt > 3 || rootReference.lockedForUpdate)) {
lockedRootReference = lockRoot(rootReference, attempt);
rootReference = lockedRootReference;
}
// 获取 root page
Page rootPage = rootReference.root;
// 向下遍历游标的位置
CursorPos pos = traverseDown(rootPage, key);
Page p = pos.page;
int index = pos.index;
tip = pos;
pos = pos.parent;
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);
}
rootPage = replacePage(pos, p, unsavedMemoryHolder);
if (lockedRootReference == null) {
if (!updateRoot(rootReference, rootPage, attempt)) {
decisionMaker.reset();
continue;
} else {
notifyWaiters();
}
}
调试结果
插入 key=4 时,root page 为空,root page 的 keys 也为空。因此将 4 直接插入 keys,将 my data 4 插入 values
调试结果:
插入 key=7 时,首先通过 traverseDown(rootPage, key) 获取 page 和 page 中 keys 的 index,然后在 page 中插入相应的 keys 和 values。keys 数组必须保持有序
调试结果
插入 key=33 时,首先通过 traverseDown(rootPage, key) 获取 page 和 page 中 keys 的 index,然后在 page 中插入相应的 keys 和 values。keys 数组必须保持有序
最终结果
调试结果
这里需求注意的一点是,父节点(非叶子节点)的 keys 数组,保存的值,是其从第二个子节点开始的 keys 数组的第一个值。
调试结果
调试结果
调试结果
调试结果
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。