Date: Mon, 22 Dec 1997 09:17:55 -0800 From: John-Mark Gurney <gurney_j@efn.org> To: Chuck Robey <chuckr@glue.umd.edu> Cc: A Joseph Koshy <koshy@india.hp.com>, freebsd-hackers@FreeBSD.ORG Subject: Re: converting drivers to dynamic memory Message-ID: <19971222091755.35537@hydrogen.nike.efn.org> In-Reply-To: <Pine.BSF.3.96.971222114303.4983Y-100000@picnic.mat.net>; from Chuck Robey on Mon, Dec 22, 1997 at 11:44:29AM -0500 References: <19971222033811.27791@hydrogen.nike.efn.org> <Pine.BSF.3.96.971222114303.4983Y-100000@picnic.mat.net>
next in thread | previous in thread | raw e-mail | index | archive | help
Chuck Robey scribbled this message on Dec 22: > On Mon, 22 Dec 1997, John-Mark Gurney wrote: > > > A Joseph Koshy scribbled this message on Dec 19: > > > >>>>>> John-Mark Gurney <gurney_j@efn.org> said: > > > For example, concurrent B-trees are supposedly very complex to implement, > > > so typically people get by locking the root node and taking the serialization > > > hit. > > > > well... I was thinking about concurrent btrees... as B-tree can be > > completely implemented as a signle downward pass > > I didn't know that ... I wonder how ... do you keep a count of keys stored > inside a node hierarchy or something like that? How is splitting handled? well... first of all B-trees have [ t-1, 2t-1 ] keys per node (the root node can have [ 1, 2t-1] keys)... and these keys subdivide the rangs of values of the tree... because of the key per node requirement, they keep track of 'em and adjust the tree as neccessary... when adding keys, the keys slowly "filter" up, until the root node contains 2t-1 keys, at which point the tree increases in height by one... then pretty much the reverse happens when deleting keys, except that the tree decreases height when the root node contains no keys... now, if your talking about splitting the tree around a key, I don't think that it possible to do that with B-trees (and keep 'em balanced)... hope this answers your questions.... P.S. I fixed the fib code so that it doesn't require floating point like it used to. -- John-Mark Gurney Modem/FAX: +1 541 683 6954 Cu Networking P.O. Box 5693, 97405 Live in Peace, destroy Micro$oft, support free software, run FreeBSD
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19971222091755.35537>