A B-Tree is upgrade or improvement to a 234 Tree. Instead of a maximum of 3 key/

Question

A B-Tree is upgrade or improvement to a 234 Tree. Instead of a maximum of 3 key/items and 4 children per node, a B-Tree lets the programmer configure the number of items and children per node. Much like the Hash Table bucket approach allows the programmer to configure the number of records per bucket, to best match the disk sector size. The B-Tree allows for matching the size of each B-Tree node to the size of a disk sector. If 4 keys/items and 5 children per node is the best fit for your disk sector, configure your B-Tree to ORDER 5 (an ORDER 5 B-Tree means a node can have at most 5 children). However, if 7 key/items and 8 children work with your disk sector size, configure an ORDER 8 B-Tree. It is the ability to customize or configure the B-Tree node that makes it an ideal choice as a data structure for storing SORTED information to a disk drive. The B-Tree is always balanced and all the leaf nodes are at the SAME level. Items in each node are in sorted order. A parent node with N key/items will have N+1 children. When you split a full node with an even number of items. LEAVE more items in the EXISTING node (move less items). Enter the keys ill order examined to find the key 58 (last one is 58):

Explanation / Answer

B-Trees :

    Recall that low-level disk I/O accesses disk by sectors . We could equate node size to sector size, and group several keys together in each node to minimize the number of I/O operations.

       Keys in internal nodes are surrounded by pointers, or record offsets, to keys that are less than or greater than, the key value. For example, all keys less than 22 are to the left and all keys greater than 22 are to the right. For simplicity, I have not shown the record address associated with each key.

B++-tree

B++-tree is included. In the implementation-dependent section, you'll need to define bAdrType and eAdrType, the types associated with B-tree file offsets and data file offsets, respectively. You'll also need to provide a callback function which is used by the B++-tree algorithm to compare keys. Functions are provided to insert/delete keys, find keys, and access keys sequentially. Function main, at the bottom of the file, provides a simple illustration for insertion.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.