B+ Tree

Definitions

1. A self-balancing tree variant where all data resides in leaf nodes (linked for efficient range scans), and internal nodes only store keys for routing. The dominant index structure in relational databases (PostgreSQL, MySQL, SQLite) and filesystems. Optimized for disk I/O — wide branching factor minimizes tree depth and disk reads.

   In plain English: The tree structure used by most databases for indexes, optimized to find data with very few disk reads.

   Example: "PostgreSQL's default index is a B+ tree — it finds any row in 3-4 disk reads regardless of table size, and range queries follow the leaf node chain."

Related Terms

• Array
• Binary Tree
• Cell Array
• Collections
• Consistency
• Record
• Skip List
• LSM Tree