B-trees includes B-Tree in the wild, B-Tree Library, API, Building and installing the BT Library, Make a program to manage a computer dictionary, Build two programs using the two BT library respectively. | B-trees anhtt-fit@ 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/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, 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: , . C++ STL: map, multimap, multiset. Linux kernel: linux/. 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 ml Notes Initiate the library #include "“ int btinit(void); The B Tree is stored in a UNIX disk file. The file can contain many B Trees, each of which is referred to by a name assigned by the user (or application). 4 API Creating a B Tree File BTA* btcrt(char* fid, int nkeys, int shared); Opening a B Tree File BTA* btopn(char* fid, int mode, int shared); Closing a B Tree .
