ConceptSystems & CS
B-tree
A B-tree is a self-balancing tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time, optimized for systems that read and write large blocks of data.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
6Each in their own terms, from the easiest level.
David J. Malan
A short, fat tree data structure where each node can have many children, used to keep search paths in a database shallow.D. Richard Hipp
A self-balancing tree data structure used for tables with 64-bit integer keys where all actual data is stored in the leaf nodes.Andy Pavlo
A self-balancing, ordered tree structure that allows searches, sequential access, insertions, and deletions in logarithmic time.Delaney Gillilan
A self-balancing tree data structure that keeps data sorted and allows efficient insertions, deletions, and searches for read-heavy workloads.Erik Demaine & Srini Devadas
A self-balancing search tree in which nodes can have more than two children and multiple keys, designed to optimize disk reads.
Lectures that assume it
13The first 12 are shown.
- Amortization: Amortized Analysis
- Sorting & Aggregation Algorithms
- Cache-Oblivious Algorithms: Searching & Sorting
- Augmentation: Range Trees
- Fusion Trees
- Dynamic Graphs II
- OpenVDB: History, Motivation, and Diverse Adoption
- Memory Hierarchy Models
- Index Concurrency Control
- Timestamp Ordering Concurrency Control
- Query Plan Transformations
- Multi-Version Concurrency Control
Connections
28The lectures that define it or assume it, and the concepts next to it.
Concepts9
- Binary search tree
- Asymptotic analysis
- Database indexes
- Database management system
- Latch Crabbing
- (2,5) Trees
Show 3 moreShow fewer
Lectures19
- SQL & Relational Databases
- AVL Trees (MIT 6.006 Introduction to Algorithms, Recitation 6)
- The Architecture and Bytecode Virtual Machine of SQLite
- R2. 2-3 Trees and B-Trees
- B+Tree Indexes
- Porting Ideas, Not Code: Reimagining Clojure and Datomic Concepts in a Language-Agnostic Data Platform
Show 13 moreShow fewer
- Amortization: Amortized Analysis
- Sorting & Aggregation Algorithms
- Cache-Oblivious Algorithms: Searching & Sorting
- Augmentation: Range Trees
- Fusion Trees
- Dynamic Graphs II
- OpenVDB: History, Motivation, and Diverse Adoption
- Memory Hierarchy Models
- Index Concurrency Control
- Timestamp Ordering Concurrency Control
- Query Plan Transformations
- Multi-Version Concurrency Control
- Databricks Photon / Spark SQL