Numbers To Know hard
With a 4KB page size and typical branching factor of 100-200, how deep is a B-Tree storing 1 Billion rows?
- A 10 to 20 levels deep
- B 3 to 5 levels deep
- C 100 levels deep
- D Exactly 2 levels deep
Answer: B. 3 to 5 levels deep
B-Trees are powerful because they are 'extremely flat'. In a typical database like PostgreSQL or MySQL, each 'page' of the tree can hold hundreds of pointers (the branching factor). If each node can point to 100 children, a tree just 5 levels deep can address 10 Billion rows ($100^5 = 10,000,000,000$). Because the top levels of the tree are always kept in the server's RAM cache, finding *any* specific row in a billion-row table typically requires only 2 to 3 mechanical disk seeks. This 'logarithmic scaling' is why B-Trees have remained the standard for database indexing for over 40 years.
One system design question a day, with spaced repetition so the ones you miss come back.
Get the appRelated questions
- What is the maximum allowed downtime per year for a system targeting '99.9%' (Three Nines) availability?
- What is the typical size of a standard ASCII character (e.g., 'A')?
- What is the typical Round Trip Time (RTT) for a single network packet traveling between New York and London (Transatlantic)?
- Network bandwidth is usually denoted in **bits** per second (Gbps), while storage is in **Bytes** (GB). What is the conversion ratio?
- Storing a password using a secure algorithm like bcrypt (cost 10) or Argon2 typically consumes how much storage per user?
- How much power does a typical fully-loaded rack-mount server consume?