Mailing-List: contact dev-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@couchdb.apache.org
Received-SPF: pass (athena.apache.org: domain of dionne@dionne-associates.com
 designates 67.222.55.9 as permitted sender)
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Apple Message framework v1257)
Subject: Re: Fundamentals Question on CoucheDB's append only b+tree.
From: Bob Dionne <dionne@dionne-associates.com>
In-Reply-To: <5293620AC1A91649BDD85E5380BC837A79A808@uksrpblkexb02.detica.com>
Date: Tue, 13 Mar 2012 13:40:09 -0400
Content-Transfer-Encoding: quoted-printable
Message-Id: <BF3BC559-FD7C-405B-9853-2266661C3221@dionne-associates.com>
References: <5293620AC1A91649BDD85E5380BC837A79A808@uksrpblkexb02.detica.com>
To: dev@couchdb.apache.org


On Mar 13, 2012, at 1:26 PM, Davies, Owain wrote:

> Hi,
>=20
> 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.
>=20
> 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.
>=20
> I do not think this can be the case, could somebody point out where I
> have made the mistake?=20

yes, the leaf nodes in couchdb are not linked

>=20
> Thanks,
>=20
> Owain
>=20
> Please consider the environment before printing this email.
>=20
> This message should be regarded as confidential. If you have received =
this email in error please notify the sender and destroy it immediately.
>=20
> Statements of intent shall only become binding when confirmed in hard =
copy by an authorised signatory.=20
>=20
> 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.
>=20
> 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.
>=20