B-Tree
Learn B-Tree (Advanced Data Structures, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
B-Tree: A Search Tree for Disk and Databases Reading from disk is slow and happens in big blocks , so a database wants a tree that is short and wide . A B-tree node holds many sorted keys (up to 2t-1 ) and has one more child than keys. All leaves are at the same depth . To insert, go down to a leaf; a node that is full is split in two and its middle key moves up. The tree grows at the root , so it stays perfectly balanced. With hundreds of keys per node, three or four reads reach any of millions of rows.