B-Tree
বি-ট্রি
এক node-এ অনেকগুলো key রাখা balanced multiway search tree — disk block আর cache line-এ মানানসই, height খুবই কম থাকে।
also: btree, b tree
BST-এ প্রতি node-এ ১টা key; minimum degree t-এর B-tree node-এ থাকে t−1 থেকে 2t−1টা key। Branching factor বড় হওয়ায় height প্রায় log_t(n) — কয়েক million key-তেও height ৩–৪।
Disk-এ random access দামি; এক node এক read-এ পুরো block নিয়ে আসে, তাই অল্প read-এ অনেক key-র সিদ্ধান্ত শেষ।
B+ tree variation-এ data শুধু leaf-এ আর leaf গুলো linked — range scan দ্রুত। Database index (PostgreSQL, MySQL InnoDB), filesystem (ext4, XFS) — সবখানে এই পরিবার।