Discussion:
Extendible Hashing - Delete
(too old to reply)
Pavel Petrenko
2011-08-09 18:54:31 UTC
Permalink
After deleting from a block,
"If nB is too small, then we perform a block merge"

When is nB considered too small?

Also, if anyone has time, can they clarify the analysis for the quad
tree range search complexity (a few posts ago).

Thank you.
Pavel
Daniel S. Roche
2011-08-10 03:08:14 UTC
Permalink
Post by Pavel Petrenko
After deleting from a block,
"If nB is too small, then we perform a block merge"
When is nB considered too small?
It depends on the implementation. It would typically be some constant
ratio of the maximum block size, like maybe S/3. Of course, we would
need the sibling block to also be sufficiently small in order to perform
a merge.

-Dan Roche
CS 240 Instructor, Section 003

Loading...