Opportunistic Garbage Collection Obviousness
Opportunistic Garbage Collection Obviousness
Posted Apr 22, 2011 6:10 UTC (Fri) by orcmid (guest, #74478)In reply to: Opportunistic Garbage Collection Obviousness by orcmid
Parent article: Google Linux servers hit with $5m patent infringement verdict (The Register)
I did go look at Berkeley DB because it does use a hashing scheme. What is revealed there is that hashing does not support indexed-sequential operation, but the B+Tree access method does. (This gets determined when you build the DB.)
The hashing method is extended linear hashing, where the hash function is adjusted dynamically to allow growing of the hash table. Linear hashing is mentioned on pp.548-549 (just before the exercises of section 6.4) of Don Knuth's "Art of Computer Programming," vol.3 Sorting and Searching, second edition. There is not enough information there to know how collisions on the same hash are dealt with.
The LWN site is currently under high scraper load, so comment display has been suppressed for anonymous users. If you are a human, you may read the comments by clicking the button below:
Note: you can avoid this step in the future by logging into your LWN account.