Let’s Invent B(+)-Trees

栏目: IT技术 · 发布时间: 4年前

内容简介:Let’s invent B(+)-trees.Say we have some things, and we want to be able to store and look them up in order. We could just put them in a big sorted array:This is great, but it’s hard to mutate – to insert or delete an element, we might have to move all the

B-trees

Let’s invent B(+)-trees.

Say we have some things, and we want to be able to store and look them up in order. We could just put them in a big sorted array:

10,20,30,40,50,60,70

This is great, but it’s hard to mutate – to insert or delete an element, we might have to move all the others!

So, instead, let’s split our array into fixed-size blocks – which can be in any order – and keep references to the blocks in sorted order:

[10,20,30,40] [50,60,70,--]

Each block is allowed to have some empty space, which we can use for insertions.

If we inserted 55 above, we’d get:

[10,20,30,40] [50,55,60,70]

So we only need to move up to a blocksworth of elements to insert into a block. What if the block we want to insert into is full? We can split a block into two halves. Say we want to insert 15 above:

[10,20,30,40] [50,55,60,70]
  [10,20,--,--] [30,40,--,--] [50,55,60,70]
  [10,15,20,--] [30,40,--,--] [50,55,60,70]

When we split a full block, it becomes half-empty. In order not to have too many blocks, we don’t permit blocks to be any emptier than that (which means at most 50% of block space is wasted).

(Deletion is mostly like insertion: If, after deleting an element, a block is less than half-full, we either merge it with its neighbor if they’re both half-full, or we move an element over from its neighbor. If it has no neighbors, we just leave it as it is.)

The next question is: How do we store the sorted list of blocks, which there might be a lot of? We can just use the same structure: Blocks indexing blocks indexing values (until the top-level list of blocks fits in a single block). This is just a tree structure.

The above is skipping over an important detail: We don’t just want blocks to be ordered, we want to be able to look our things up by key. So for each block we want to know the range of keys it can contain. If a block contains keys, that’s easy – the range is [first,last]. If a block contains blocks, we could store the full range of each subblock –

(l1,r1)   (l2,r2)   (l3,r3)   (l4,r4)
  [   b1,       b2,       b3,       b4   ]

– but we really just care about finding the right block, so l1 and r4 are irrelevant, and r1/l2,r2/l3,r3/l4 are redundant – any value in that range would work, since it just tells us which side to descend into. So we just need to store n-1 keys:

l2       l3     l4
  [  b1,     b2,     b3,     b4   ]

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

LaTeX入门

LaTeX入门

刘海洋 / 电子工业出版社 / 2013-6-1 / CNY 79.00

LaTeX 已经成为国际上数学、物理、计算机等科技领域专业排版的实际标准,其他领域(化学、生物、工程、语言学等)也有大量用户。本书内容取材广泛,涵盖了正文组织、自动化工具、数学公式、图表制作、幻灯片演示、错误处理等方面。考虑到LaTeX 也是不断进化的,本书从数以千计的LaTeX 工具宏包中进行甄选,选择较新而且实用的版本来讲解排版技巧。 为了方便读者的学习,本书给出了大量的实例和一定量的习......一起来看看 《LaTeX入门》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试