3 ms·

Hash table updates are quick until you have to rehash. Rehashing can be done in the background, but then you had added code complexity, you'll be doing signifi

• makmanalp 10y ago
  So this is a great point that I forgot about. Yes, it's a problem for sure, but definitely not unaddressable. The databases community has been thinking about hashing schemes that address this issue since the 80s, like linear hashing, extendible hashing and consistent hashing. The trick is often around amortizing the cost of rehashing over insertions (no background tasks needed!), or somehow minimizing the amount of remapping and rehashing that needs to be done by using clever positioning. So yeah, like anything, it's a tradeoff and not a cure-all, but it can be done quite well.
• infogulch 10y ago
  Rehashing can be incremental. 1: Allocate a new table of size at least 2X. 2: All accesses to the table hit both the old and new tables. 3: Inserts only go in new. 4: Any change (insert, update, delete) also moves 2 other elements. You can prevent a O(n) rescan at 4 by keeping a single persistent cursor that scans through the old table from top to bottom. There, still O(1) throughout (C may go up by 2-3 but that's still small). And only uses 1.5x memory. Not saying that's what postgres does here (it uses WAL, so probably not exactly).
• neilc 10y ago
  Postgres hash indexes use linear hashing, which effectively means that rehashing/expansion is done incrementally: https://en.wikipedia.org/wiki/Linear_hashing https://en.wikipedia.org/wiki/Linear_hashing