4 ms·
Insertion should still be extremely fast for such a small index, right? Doing binary search over a b-tree page is <100 cycles. b-tree traversal over 100M recor
by vjerancrnjak 3y ago
Insertion should still be extremely fast for such a small index, right?
Doing binary search over a b-tree page is <100 cycles. b-tree traversal over 100M records should still be measured in microseconds and binary search over that should be in microseconds too if not in 100s of nanoseconds.
- lazide 3y ago‘It depends’ - don’t forget about locking overhead, needing to flush multiple pages/leafs as thresholds get hit, disk I/O wait times, etc. At the beginning it’s rarely noticeable, but it does exist and under heavy load or with a lot of index writes needing to happen it can cause very noticeable overhead.
- vjerancrnjak 3y agoYes, but these bits don’t scale with log(n) index tree. They depend on something other than the index data structure.
- lazide 3y agoUsually load.
- hinkley 3y agoThis conversation is about unrepresentative sample data.
- vjerancrnjak 3y agoAre you saying that the index is made on columns which only have few unique values so you need to scan everything all the time? Given that you’ve included the log(b) claim I thought you were referring to a normally functioning btree. A situation where 65k rows end up slowing down things severely should have more to do with other database features (foreign keys and similar).