B-trees anhtt-fit@mail.hut.edu.vn B tree A B-Tree of order m (the maximum number of children for each node) is a tree which satisfies the following properties : Every node has <= m children. Every node ( except root and leaves ) has >= m/2 children. The root has at least 2 children. All leaves appear in the same level A non-leaf node with k children contains k – 1 keys 1 B-Tree Generalizes 2-3-4 trees by allowing up to M links per node. Main application: file systems. Reading a page into memory from disk is expensive. Accessing info on a page in memory is free. Goal: minimize # page accesses. Node size M = page size. Space-time tradeoff. M large ! only a few levels in tree. M small ! less wasted space. Number of page accesses is logMN per op. Typical M = 1000, N < 1 trillion. Example TELSTRA: customer billing database with 51 billion rows, 4.2 terabytes of data. Databases cannot be maintained entirely in memory, b-trees are often used to index the data and to provide fast access. 2 Search B-Tree in the wild Red-black trees: widely used as system symbol tables Java: java.util.TreeMap, java.util.TreeSet. C++ STL: map, multimap, multiset. Linux kernel: linux/rbtree.h. B-Trees: widely used for file systems and databases Windows: HPFS. Mac: HFS, HFS+. Linux: ReiserFS, XFS, Ext3FS, JFS. Databases: ORACLE, DB2, INGRES, SQL, PostgreSQL All nodes in B-Tree are assumed to be stored in secondary storage (disk) rather than primary storage (memory), There basic operations for accessing a page: DiskRead(), Disk-Write(), Allocate-Node() 3 B-Tree Library Software and documentation is accessed at http://www.hydrus.org.uk/doc/bt/html/index.ht ml Notes Initiate the l