stratified B-trees

stratified B-trees

[Karn Kallio]

I just noticed this out today on the arXiv : http://xxx.lanl.gov/abs/1103.4282 
The paper describes "stratified B-trees" and quoting from the abstract:

"
We describe the `stratified B-tree', which beats the CoW B-tree in every way. 
In particular, it is the first versioned dictionary to achieve optimal 
tradeoffs between space, query and update performance. Therefore, we believe 
there is no longer a good reason to use CoW B-trees for versioned data stores.
"

The paper mentions that a company called "Acunu" is developing an 
implementation.  

Are these stratified B-trees something which the btrfs project could use?

Re: stratified B-trees

[Andi Kleen]

Karn Kallio <tierpluspluslists@gmail.com> writes:

> Are these stratified B-trees something which the btrfs project could use?

The current b*tree is pretty much hardcoded in the disk format, so it 
would be hard to change in a compatible way.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only

Re: stratified B-trees

[Ezra Ulembeck]

On Wed, Mar 23, 2011 at 5:38 PM, Karn Kallio
<tierpluspluslists@gmail.com> wrote:
> I just noticed this out today on the arXiv : http://xxx.lanl.gov/abs/=
1103.4282
> The paper describes "stratified B-trees" and quoting from the abstrac=
t:
>


LOL.
It looks like this paper is generated by a robot:

"... Stratified B-trees don=92t need block-size tuning, unlike B-trees.
One major advantage is that they are naturally good candidates for
SSDs =96 the Intel X25M can perform 35,000 random 4K reads/s,
but must write in units of many MBs in order to fully utilise its perfo=
rmance.
This massive asymmetry in block size makes life very hard..."

How do you like:
"to utilise performance",
"massive asymmetry in block size"..


> "
> We describe the `stratified B-tree', which beats the CoW B-tree in ev=
ery way.
> In particular, it is the first versioned dictionary to achieve optima=
l
> tradeoffs between space, query and update performance. Therefore, we =
believe
> there is no longer a good reason to use CoW B-trees for versioned dat=
a stores.
> "
>
> The paper mentions that a company called "Acunu" is developing an
> implementation.
>
> Are these stratified B-trees something which the btrfs project could =
use?
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs=
" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at =A0http://vger.kernel.org/majordomo-info.html
>
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" =
in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html