Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/9 • [previous page] • [next page] • [PDF]
| [+] Memory hierarchy: models, cache-oblivious B-trees | ||||
| The topic of the next three lectures is cache-efficient data structures. A classic result here is that B-trees are good at exploiting that data is transferred in blocks between cache and main memory, and between main memory and disk, and so on. B-trees achieve O(logB N) insert/delete/predecessor/ successor for N items and memory block transfers of size B. What's more recent and surprising is that you can achieve the same performance even if you don't know what B is, or in other words, simultaneously for all architectures with all values of B. This is a result in the “cache-oblivious” model, and we'll see how to do it over the next two lectures. Cache-oblivious data structures show some exciting practical promise, too, as they form the foundation of a database startup, Tokutek. | ||||
|
Lecture notes, page 1/9 •
[previous page] •
[next page] •
[PDF]
Lecture notes, page 1/9 • [previous page] • [next page] • [PDF] |
|
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The lecture notes should advance automatically. If you have any trouble with playback, email Erik.