Re:Hash indexes are faster than btree indexes?
by infogulch on Monday March 20, 2017 @11:37AM
(#13915046)
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).
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).