Feels like a digression off the actual tree structure, but isn't this incorrect, since a hash map can do key lookups in O(1)? With caveats, of course.
It's a great idea over all, but I'd also be curious how well overlaying an event log on a cuckoo hash would work in comparison.
[1] http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-p...
That said, when a Cuckoo hash gets very full and bounces entries around a lot, there might be an advantage to buffering operations and choosing insertion patterns that reduce the batch's insertion time. Then again, Cuckoo hashes already perform so well for situations they're designed for, so it's hard to improve them with an event log overlay.
No, because log(n) might be smaller than the word size of the machine, which is the common case for hash table implementations.
This is a very old discussion. Read Knuth's rationale. Then read the similar sections in Segwick et all or whatever other basic competence textbook on algorithms you like. Compare them, think about which contexts each approach is most useful in.
In other words, no, you have not somehow cleverly invalidated all of complexity analysis.