B-Tree

Presentation Summary

In this notebook (html), I present how B+trees work. You’ll need to download this code and install pydot, probably. B-trees are ubiquitous database structures, used in the NTFS, HFS, and Ext4 file system formats, among others. The reason is simple: O(log(N)) overhead, O(log(N)) lookup, O(log(N)) deletion, and its nodes can be adjusted to fill disk blocks or caches. They excel whenever an algorithm utilizes large, slow memory access combined with small, fast memory access. Some easy examples are disk and RAM, RAM an cache, and others.

All data structures.

• by Brian Busemeyer · B-Tree