Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Logarithmic merge

  • Maintain a series of indexes, each twice as large as the previous one

    • At any time, some of these powers of 2 are instantiated

  • Keep smallest (Z0) in memory

  • Larger ones (I0, I1, …) on disk

  • If Z0 gets too big (> n), write to disk as I0

  • or merge with I0 (if I0 already exists) as Z1

  • Either write merge Z1 to disk as I1 (if no I1)

  • Or merge with I1 to form Z2


Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.