B-Tree

noun

say it: “BEE TREE” /biː triː/

A balanced tree whose nodes each hold many sorted keys, so it's only a few levels tall; databases use it for indexes.

What is a B-tree?

A B-tree packs many sorted keys into each node, so a node has many children and the tree is very short: three levels can tell a billion rows apart. Reading from disk comes a page at a time, so databases build their indexes as B-trees.

In a sentence

  • “The database index is a B-tree, so finding one customer among a billion takes about three page reads.”

Level: Freelancer · More Data Structures terms at this level

Updated