lkml.org 
[lkml]   [1998]   [Sep]   [18]   [last100]   RSS Feed
Views: [more markup]  [less markup]  [headers]  [forward] 
 
Messages in this thread
/
From"Helge Hafting" <>
DateFri, 18 Sep 1998 09:35:21 +0100
SubjectRe: AVL and hash in memory management
In <199809151131.EAA10342@dm.cobaltmicro.com>, on 09/15/98 
   at 04:31 AM, "David S. Miller" <davem@dm.cobaltmicro.com> said:

>   From: "Koshelev Maximka" <iloveselfme@hotmail.com>
>   Date: 	Tue, 15 Sep 1998 01:56:29 PDT

>   I am thinking this method can give better perfomance becouse tree 
>   becomes smaller in N times, where N is a number of elements in hash 
>   array.

>It is an interesting data structure, thanks for presenting it. But it
>still has one of the fundamental problems we were trying to remove by
>going to a non-tree mechanism, the balancing cost.

Seems to me that the suggested structure offer the best of both worlds:
The cases with few items won't have much balancing cost because the hash
array ensures that most trees have a root node only.

Cases with lots of items will have balancing cost, but they will also
benefit from the trees.

Helge Hafting
-- 
-----------------------------------------------------------
helge.hafting@daldata.no
-----------------------------------------------------------

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:44    [from the cache]
©2003-2008