couchdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Davies, Owain" <Owain.Dav...@baesystemsdetica.com>
Subject RE: Fundamentals Question on CoucheDB's append only b+tree.
Date Tue, 13 Mar 2012 17:44:31 GMT
Thanks,
That clears it all up, and makes more sense now.

Owain 

-----Original Message-----
From: Robert Newson [mailto:rnewson@apache.org] 
Sent: 13 March 2012 17:41
To: dev@couchdb.apache.org
Subject: Re: Fundamentals Question on CoucheDB's append only b+tree.

There's no linked list running between the leafs. A b+tree doesn't
require one, though it's a common addition. The b+tree algorithm is a
revision over a binary tree (where inner nodes point strictly at one
left and one right item). To be a b+tree you need to hold many pointers
on an inner node.

B.

On 13 March 2012 17:26, Davies, Owain
<Owain.Davies@baesystemsdetica.com> wrote:
> Hi,
>
> I have been reading the couchDB guide, particularly the appendix on 
> the power of b-trees. As I understand it couchdb uses a b+tree, in 
> which the leaf nodes have pointers to their siblings to facilitate 
> quick in-order and reverse in-order enumeration of the documents in
the b+tree.
>
> When a document is modified (or added), then the document is appended 
> to the file, the leaf node is cloned and updated to point to the new 
> document. However in order to maintain the linked list between the 
> sibling leaf nodes, you would need to update the adjacent link nodes 
> (creating new leaf nodes appended onto the end of the file), this will

> eventually require that the whole tree is replicated, not just the 
> node on the path to the effected leaf node.
>
> I do not think this can be the case, could somebody point out where I 
> have made the mistake?
>
> Thanks,
>
> Owain
>
> Please consider the environment before printing this email.
>
> This message should be regarded as confidential. If you have received
this email in error please notify the sender and destroy it immediately.
>
> Statements of intent shall only become binding when confirmed in hard
copy by an authorised signatory.
>
> The contents of this email may relate to dealings with other companies
under the control of BAE Systems plc details of which can be found at
http://www.baesystems.com/Businesses/index.htm.
>
> Detica Limited is a BAE Systems company trading as BAE Systems Detica.
> Detica Limited is registered in England and Wales under No: 1337451.
> Registered office: Surrey Research Park, Guildford, Surrey, GU2 7YP,
England.
>
Please consider the environment before printing this email.
 
This message should be regarded as confidential. If you have received this email in error
please notify the sender and destroy it immediately.
 
Statements of intent shall only become binding when confirmed in hard copy by an authorised
signatory. 
 
The contents of this email may relate to dealings with other companies under the control of
BAE Systems plc details of which can be found at http://www.baesystems.com/Businesses/index.htm.
 
Detica Limited is a BAE Systems company trading as BAE Systems Detica.
Detica Limited is registered in England and Wales under No: 1337451.
Registered office: Surrey Research Park, Guildford, Surrey, GU2 7YP, England.


Mime
View raw message