* stratified B-trees
@ 2011-03-23 16:38 Karn Kallio
2011-03-23 18:01 ` Andi Kleen
2011-03-23 18:11 ` Ezra Ulembeck
0 siblings, 2 replies; 3+ messages in thread
From: Karn Kallio @ 2011-03-23 16:38 UTC (permalink / raw)
To: linux-btrfs
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?
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: stratified B-trees
2011-03-23 16:38 stratified B-trees Karn Kallio
@ 2011-03-23 18:01 ` Andi Kleen
2011-03-23 18:11 ` Ezra Ulembeck
1 sibling, 0 replies; 3+ messages in thread
From: Andi Kleen @ 2011-03-23 18:01 UTC (permalink / raw)
To: linux-btrfs; +Cc: tierpluspluslists
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: stratified B-trees
2011-03-23 16:38 stratified B-trees Karn Kallio
2011-03-23 18:01 ` Andi Kleen
@ 2011-03-23 18:11 ` Ezra Ulembeck
1 sibling, 0 replies; 3+ messages in thread
From: Ezra Ulembeck @ 2011-03-23 18:11 UTC (permalink / raw)
To: Karn Kallio; +Cc: linux-btrfs
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
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2011-03-23 18:11 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-03-23 16:38 stratified B-trees Karn Kallio
2011-03-23 18:01 ` Andi Kleen
2011-03-23 18:11 ` Ezra Ulembeck
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).