Learned readers will ask themselves: so why use an unbalanced tree instead of balanced one, which offers better asymptotic times https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree?

Likely:
* the maximum number of entries is small enough due to memory size limitations, that we won't waste too much memory with the root directory entry
* different entries would have different levels, and thus different access times
* tree rotations would likely make caching more complicated


X86 paging/why not a balanced tree

ID: x86-paging/why-not-a-balanced-tree