[PATCH v2 1/2] lib/htree: Add locking interface to new Hash Tree

[lsahn at wewakecorp.com]

> -----Original Message-----
> From: owner-linux-mm at kvack.org <owner-linux-mm at kvack.org> On Behalf Of
> JaeJoon Jung
> Sent: Wednesday, August 7, 2024 9:22 AM
> To: Greg Kroah-Hartman <gregkh at linuxfoundation.org>
> Cc: Linus Torvalds <torvalds at linux-foundation.org>; Sasha Levin
> <levinsasha928 at gmail.com>; Liam R . Howlett <Liam.Howlett at oracle.com>;
> Matthew Wilcox <willy at infradead.org>; linux-kernel at vger.kernel.org; linux-
> mm at kvack.org; maple-tree at lists.infradead.org; linux-
> fsdevel at vger.kernel.org
> Subject: Re: [PATCH v2 1/2] lib/htree: Add locking interface to new Hash
> Tree

...
 
> The Hash Tree I implemented manages the Tree with the characteristic
> of a hash that is accessed in O(1).
> Even if the tree gets deeper, the search time does not increase.
> There is no rotation cost because the tree is kept balanced by hash key.

How does it keep balancing?