While just about any "constant-time" operation gets a log N factor, given large enough N, the TLB issue is mostly surmountable. Assuming you do want to keep us

While just about any "constant-time" operation gets a log N factor, given large enough N, the TLB issue is mostly surmountable. Assuming you do want to keep using virtual memory, you can not-simply¹ use huge pages and avoid the log N TLB factor. Which is a big thing, because TLB misses are very costly, so it can be worth it, even though you are giving up a lot of the paged-memory benefits. ¹ Lots of limitations and caveats. Your MMU needs big enough pages with a reasonable amount of TLB entries. Managing memory becomes more difficult. Your CPU likely has few large TLB entries, so only certain size ranges fit, etc.