From owner-freebsd-hackers Mon Dec 22 09:23:21 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id JAA07667 for hackers-outgoing; Mon, 22 Dec 1997 09:23:21 -0800 (PST) (envelope-from owner-freebsd-hackers) Received: from hydrogen.nike.efn.org (resnet.uoregon.edu [128.223.170.28]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id JAA06932 for ; Mon, 22 Dec 1997 09:18:06 -0800 (PST) (envelope-from gurney_j@efn.org) Received: (from jmg@localhost) by hydrogen.nike.efn.org (8.8.7/8.8.7) id JAA08688; Mon, 22 Dec 1997 09:17:56 -0800 (PST) Message-ID: <19971222091755.35537@hydrogen.nike.efn.org> Date: Mon, 22 Dec 1997 09:17:55 -0800 From: John-Mark Gurney To: Chuck Robey Cc: A Joseph Koshy , freebsd-hackers@FreeBSD.ORG Subject: Re: converting drivers to dynamic memory References: <19971222033811.27791@hydrogen.nike.efn.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 0.69 In-Reply-To: ; from Chuck Robey on Mon, Dec 22, 1997 at 11:44:29AM -0500 Reply-To: John-Mark Gurney Organization: Cu Networking X-Operating-System: FreeBSD 2.2.1-RELEASE i386 X-PGP-Fingerprint: B7 EC EF F8 AE ED A7 31 96 7A 22 B3 D8 56 36 F4 X-Files: The truth is out there X-URL: http://resnet.uoregon.edu/~gurney_j/ Sender: owner-freebsd-hackers@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk 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 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