couchdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Robert Newson <rnew...@apache.org>
Subject Re: Fundamentals Question on CoucheDB's append only b+tree.
Date Tue, 13 Mar 2012 17:40:54 GMT
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.
>

Mime
View raw message