Scribd
Upload
20 views8 pages

B Tree

hj

Uploaded by

Bhargav Reddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
20 views8 pages

B Tree

hj

Uploaded by

Bhargav Reddy
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
You are on page 1/ 8
250, 296 PM Intadicton of + Tre - GeoksterGeeks TutorialsDSAData ScienceWeb TechCourses oS Aptitude Engineering Mathematics Discrete Mathematics Operating System DBMS Computer Networks Introduction of B+ Tree Last Updated : 08 Mar, 2024 B + Tree is a variation of the B-tree data structure. In a B + tree, data pointers are stored only at the leaf nodes of the tree. In a B+ tree structure of a leaf node differs from the structure of internal nodes. The leaf nodes have an entry for every value of the search field, along with a data pointer to the record (or to the block that contains this record). The leaf nodes of the B+ tree are linked together to provide ordered access to the search field to the records. Internal nodes of a B+ tree are used to guide the search. Some search field values from the leaf nodes are repeated in the internal nodes of the B+ tree. Features of B+ Trees + Balanced: B+ Trees are self-balancing, which means that as data is added or removed from the tree, it automatically adjusts itself to maintain a balanced structure. This ensures that the search time remains relatively constant, regardless of the size of the tree. + Multi-level: B+ Trees are multi-level data structures, with a root node at the top and one or more levels of internal nodes below it. The leaf nodes at the bottom level contain the actual data. * Ordered: B+ Trees maintain the order of the keys in the tree, which makes it easy to perform range queries and other operations that require sorted data. + Fan-out: B+ Trees have a high fan-out, which means that each node can have many child nodes. This reduces the height of the tree and increases the efficiency of searching and indexing operations. * Cache-friendly: B+ Trees are designed to be cache-friendly, which means that they can take advantage of the caching mechanisms in modern computer architectures to improve performance. * Disk-oriented: B+ Trees are often used for disk-based storage systems because they are efficient at storing and retrieving data from disk. Why Use B+ Tree? tips. geekstorgecks.orgintroduction-oF brea! a3. szsree, 1298 PM Introduction of 8+ Tre -GuokalrGeoks + B+ Trees are the best choice for storage systems with sluggish data access because they minimize I/O operations while facilitating efficient disc access * B+ Trees are a good choice for database systems and applications needing quick data retrieval because of their balanced structure, which guarantees predictable performance for a variety of activities and facilitates effective range-based queries. Difference Between B+ Tree and B Tree Some differences between B+ Tree and B Tree are stated below. et] Parameters B+ Tree B Tree Separate leaf nodes for data Nodes store both keys and Structure storage and internal nodes data values for indexing Leaf nodes form a linked list LeafNodes for efficient range-based Leaf nodes do not form a linked list queries Order Higher order (more keys) Lower order (fewer keys) Key Typically —allows_—key_-_ Usually does not allow key Duplication duplication in leaf nodes duplication tips. geekstorgecks.orgintroduction-oF brea! ans 4125124, 12:56 PM Introduction of 8+ Tree - GecksforGeeks Parameters B+ Tree B Tree Better disk access due to More disk 0 due to non- Disk Access sequential reads in a linked sequential reads in internal list structure nodes Database systems, _ file In-memory data structures, Applications systems, where range databases, general-purpose queries are common use Better performance for range Balanced performance for Performance queries and bulk data’ search, insert, and delete retrieval operations . Requires less memory as keys Memory Requires more memory for and values are stored in the Usage internal nodes same node Implementation of B+ Tree In order, to implement dynamic multilevel indexing, B-tree and B+ tree are generally employed. The drawback of the B-tree used for indexing, however, is that it stores the data pointer (a pointer to the disk file block containing the key value), corresponding to a particular key value, along with that key value in the node of a B-tree. This technique greatly reduces the number of entries that can be packed into a node of a B-tree, thereby contributing to the increase in the number of levels in the B-tree, hence increasing the search time of a record. B+ tree eliminates the above drawback by storing data pointers only at the leaf nodes of the tree. Thus, the structure of the leaf nodes of a B+ tree is quite different from the structure of the internal nodes of the B tree. It may be noted here that, since data pointers are present only at the leaf nodes, the leaf nodes must necessarily store all the key values along with their corresponding data pointers to the disk file block, in order to access them. Moreover, the leaf nodes are linked to providing ordered access to the records. The leaf nodes, therefore form the first level of the index, with the internal nodes forming the other levels of a multilevel index. Some of the tips. geekstorgecks.orgintroduction-oF brea! 33 szsree, 1298 PM Introduction of 8+ Tre -GuokalrGeoks key values of the leaf nodes also appear in the internal nodes, to simply act as a medium to control the searching of a record. From the above discussion, it is apparent that a B+ tree, unlike a B-tree, has two orders, ‘a’ and ‘b’, one for the internal nodes and the other for the external (or leaf) nodes. [>>] Structure of B+ Trees ee B+ Trees contain two types of nodes: hitps:lvww.geoksforgesks orgintroducton-of bree! 4ns 12824, 12:98 PM Irroduction of 8+ Tree - GeeksorGeoks * Internal Nodes: Internal Nodes are the nodes that are present in at least n/2 record pointers, but not in the root node, * Leaf Nodes: Leaf Nodes are the nodes that have n pointers. The Structure of the Internal Nodes of a B+ Tree of Order ‘a’ is as Follows * Each internal node is of the form: where ¢ <=a and each P is a tree pointer (i.e points to another node of the tree) and, each K; is a key-value (see diagram-| for reference) + Every internal node has : Ki < Kz <... < Ket * For each search field value *X’ in the sub-tree pointed at by Pj, the following condition holds: Ki-1 < X <= Ki, for 1 << cand, Ki-1 , Phext® where c <= b and each D; is a data pointer (i.e points to actual record in the disk whose key value is K; or to a disk file block containing that record) and, each K; is a key value and, Prext points to next leaf node in * Each leaf node is of the form: <, , the B+ tree (see diagram II for reference) * Every leaf node has : Ky < Ky

You might also like