OurBigBook About$ Donate
 Sign in+ Sign up
by Ciro Santilli (@cirosantilli, 37)

x86 Paging Tutorial / Why not a balanced tree

 ... Processor (computing) Instruction set architecture List of instruction set architectures x86 x86 Paging Tutorial Example: multi-level paging scheme
 0 By others on same topic  0 Discussions  Updated 2025-05-26  +Created 1970-01-01  See my version
Learned readers will ask themselves: so why use an unbalanced tree instead of balanced one, which offers better asymptotic times 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

 Ancestors (13)

  1. Example: multi-level paging scheme
  2. x86 Paging Tutorial
  3. x86
  4. List of instruction set architectures
  5. Instruction set architecture
  6. Processor (computing)
  7. Computer hardware component type
  8. Computer hardware
  9. Computer
  10. Information technology
  11. Area of technology
  12. Technology
  13.  Home

 View article source

 Discussion (0)

+ New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic + Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook