B-tree index for dummies

B-tree index for dummies

Basic B-tree index

 a b c d e f g  h i j k l m n o         p q r s t u v   w x y z æ ø å

0                                  o
                                   |
                   |-------------------------------|
1                  g                               v
                   |                               |
           |---------------|               |---------------|
2          d               k               s               z
           |               |               |               |
       |-------|       |-------|       |-------|       |-------|
3      b       f       i       m       q       u       x       ø
       |       |       |       |       |       |       |       |
     |---|   |---|   |---|   |---|   |---|   |---|   |---|   |---|
4    a   c   e       h   j   l   n   p   r   t       w   y   æ   å


2^5  =              32 rows
2^6  =              64 rows
2^7  =             128 rows
2^8  =             256 rows
2^9  =             512 rows
2^10 =           1.024 rows
2^11 =           2.048 rows
2^12 =           4.096 rows
2^13 =           8.192 rows
2^14 =          16.384 rows
2^15 =          32.768 rows
2^16 =          65.536 rows
2^17 =         131.072 rows
2^18 =         262.144 rows
2^19 =         524.288 rows
2^20 =       1.048.576 rows
2^21 =       2.097.152 rows
2^22 =       4.194.304 rows
2^23 =       8.388.608 rows
2^24 =      16.777.216 rows
2^25 =      33.554.432 rows
2^26 =      67.108.864 rows
2^27 =     134.217.728 rows
2^28 =     268.435.456 rows
2^29 =     536.870.912 rows
2^30 =   1.073.741.824 rows
2^31 =   2.147.483.648 rows
2^32 =   4.294.967.296 rows
2^33 =   8.589.934.592 rows
2^34 =  17.179.869.184 rows
2^35 =  34.359.738.368 rows
2^36 =  68.719.476.736 rows
2^37 = 137.438.953.472 rows
2^38 = 274.877.906.944 rows

Alphabet lookup

  • To find a letter in the alphabet takes an average of 29/2 = 14,5 comparisons without an index.
  • With an index this can be done with an average of 3 comparisons.

Real world example

...to be continued...