LACROSSE UNIVERSITY
B-Trees
A PAPER SUBMITTED TO
THE FACULTY OF THE DIVISON OF SCIENCES
IN CANDIDACY FOR THE DEGREE OF
MASTER OF SCIENCE
DEPARTMENT OF COMPUTER SCIENCE
By
Ayesha Asghar
December 18, 2006
Copyright © 2006 by Ayesha Asghar
All rights reserved
To Zainab
If we believe in data structures, we must believe in independent (hence simultaneous) processing. For why else would we collect items within a structure? Why do we tolerate languages that give us the one without the other?
Epigrams in Programming
CONTENTS
ILLUSTRATIONS................. vi
PREFACE................. vii
ACKNOWLEDGEMENTS................. viii
1. Introduction 1
1.1. Purpose 1
1.2. Scope 1
2. B-Trees 2
2.1. Structure of B Trees 2
2.2. Height of B Trees 4
2.3. Operations on B Trees 5
2.3.1. B-Tree Search 5
2.3.2. B-Tree Create 6
2.3.3. B-Tree Split-Child 7
2.3.4. B-Tree Insert 8
2.3.5. B-Tree Insert-Nonfull 8
2.3.6. B-Tree-Delete 9
3. B-Trees Examples 10
3.1. B-Tree Insert 10
3.2. B-Tree Delete 13
4. Implementing B-Trees 19
5. Application of B-Trees 22
5.1. Databases 22
5.2. Concurrent Access to B-Trees 23
6. Variants of B-Trees 25
6.1. B+-Trees 25
6.2. B*-Trees 25
6.3. Trade offs 25
7. Conclusion 26
Bibliography................. 28
ILLUSTRATIONS
Figure Page
PREFACE
The aim of this Applied Knowledge Paper is to give a deep insight on the need, concepts and application of B-Trees.
The document starts by giving a brief introduction to B-Trees. It entails the structure of B-Trees and gives a comprehensive definition for it.
Further the operations on B-Trees have been discussed in details. The algorithm/code for these operations has been provided as well for a better understanding.
Next to this, comprehensive examples of the operations on B-Trees have been given. And then the application of the B-trees has been talked about, where the uses and advantage of B-Trees have been stressed upon. Next the different variations of B-Trees are elucidated.
Finally, the document wraps up the paper by critically evaluating merits and demerits of B-Trees. The author of the paper hopes that this discussion will serve as a comprehensive guideline for the readers.
ACKNOWLEDGEMENTS
I would like to thank the auspicious instructors of Lacrosse University under whose guidance I’ve been able to come up with this report. I thank them for their cooperation through out and also for resolving all problems and every issue that I faced.
Next, I would like to thank my family who provided me with all the sources and material required for making this possible. Lastly; I would like to thank God Almighty who gave me the strength and will power to complete this piece of work.
1. Introduction
1.1. Purpose
The purpose of this paper is to describe a well-formed and a thorough analysis of the B-Trees. This paper also gives an introduction into the structure of B-Trees with detailed examples.
It focuses on the operations on B-Trees and discusses in-detail their structure with help of extensive examples.
This paper provides an understanding of the need and benefits of B-Trees and also concentrates on its application. The variations of B-Trees have also been discussed.
This paper will assist the novice programmers to have a better understanding of B-Trees and its operations implemented and its uses. While, the expert programmers will also agree upon the concept details provided.
1.2. Scope
The paper provides answers to what, when, how and who questions related to B-Trees, such as:
§ What is a B-Tree?
§ What is the height of a B-Tree?
§ What are the operations supported by B-Trees?
§ Applications of B-Trees.
§ Variants of B-Trees.
2. B-Trees
Tree structures support various basic dynamic set operations including Search, Predecessor, Successor, Minimum, Maximum, Insert, and Delete in time proportional to the height of the tree. Ideally, a tree will be balanced and the height will be log n where n is the number of nodes in the tree. To ensure that the height of the tree is as small as possible and therefore provide the best running time, a balanced tree structure like a red-black tree, AVL tree, or b-tree must be used.
When working with large sets of data, it is often not possible or desirable to maintain the entire structure in primary storage (RAM). Instead, a relatively small portion of the data structure is maintained in primary storage, and additional data is read from secondary storage as needed. Unfortunately, a magnetic disk, the most common form of secondary storage, is significantly slower than random access memory (RAM). In fact, the system often spends more time retrieving data than actually processing data.
B-trees are balanced trees that are optimized for situations when part or the entire tree must be maintained in secondary storage such as a magnetic disk. Since disk accesses are expensive (time consuming) operations, a b-tree tries to minimize the number of disk accesses. For example, a b-tree with a height of 2 and a branching factor of 1001 can store over one billion keys but requires at most two disk accesses to search for any node (Cormen et al. 1998, p. 384).
2.1. Structure of B Trees
Unlike a binary-tree, each node of a b-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Each key has an associated child that is the root of a sub-tree containing all nodes with keys less than or equal to the key but greater than the preceding key. A node also has an additional rightmost child that is the root for a sub-tree containing all keys greater than any keys in the node.
A b-tree has a minimum number of allowable children for each node known as the minimization factor. If t is this minimization factor, every node must have at least t - 1 keys. Under certain circumstances, the root node is allowed to violate this property by having fewer than t - 1 keys. Every node may have at most 2t - 1 keys or, equivalently, 2t children.
Since each node tends to have a large branching factor (a large number of children), it is typically necessary to traverse relatively few nodes before locating the desired key. If access to each node requires a disk access, then a b-tree will minimize the number of disk accesses required. The minimization factor is usually chosen so that the total size of each node corresponds to a multiple of the block size of the underlying storage device. This choice simplifies and optimizes disk access. Consequently, a b-tree is an ideal data structure for situations where all data cannot reside in primary storage and accesses to secondary storage are comparatively expensive (or time consuming).
In short, A B-tree of order m is an ordered tree which satisfies the following properties:
§ Every node has at most m children.
§ Every node, except the root, has at least m/2 children.
§ The root has at least 2 children.
§ All leaves occur on the same level.
B-trees were introduced by Bayer and McCreight in 1972 (they did not explain their choice of name). They are balanced search trees designed to work well on magnetic disks or other direct-access secondary storage devices. B-trees are similar to red-black trees in that every n-node B-tree has height O(lg n), although the height of a B-tree can be considerably less than that of a red-black tree because its branching factor can be much larger. Therefore, B-trees can also be used to implement many dynamic-set operations in time O(lg n).
The standard representation adopted here is a sequence of number of children of each internal node, where the nodes are traversed bottom-up level-by-level and from right-to-left within a level. See the following figure for an example:
2.2. Height of B Trees
For n greater than or equal to one, the height of an n-key b-tree T of height h with a minimum degree t greater than or equal to 2,
For a proof of the above inequality, refer to (Cormen et al. 1998, pp. 383-384)
The worst case height is O(log n). Since the "branchiness" of a b-tree can be large compared to many other balanced tree structures, the base of the logarithm tends to be large; therefore, the number of nodes visited during a search tends to be smaller than required by other tree structures. Although this does not affect the asymptotic worst case height, b-trees tend to have smaller heights than other trees with the same asymptotic height.
2.3. Operations on B Trees
The algorithms for the search, create, and insert operations are shown below. Note that these algorithms are single pass; in other words, they do not traverse back up the tree. Since b-trees strive to minimize disk accesses and the nodes are usually stored on disk, this single-pass approach will reduce the number of node visits and thus the number of disk accesses. Simpler double-pass approaches that move back up the tree to fix violations are possible.
Since all nodes are assumed to be stored in secondary storage (disk) rather than primary storage (memory), all references to a given node be preceded by a read operation denoted by Disk-Read. Similarly, once a node is modified and it is no longer needed, it must be written out to secondary storage with a write operation denoted by Disk-Write. The algorithms below assume that all nodes referenced in parameters have already had a corresponding Disk-Read operation. New nodes are created and assigned storage with the Allocate-Node call. The implementation details of the Disk-Read, Disk-Write, and Allocate-Node functions are operating system and implementation dependent.
2.3.1. B-Tree Search
The search operation on a b-tree is analogous to a search on a binary tree. Instead of choosing between a left and a right child as in a binary tree, a b-tree search must make an n-way choice. The correct child is chosen by performing a linear search of the values in the node. After finding the value greater than or equal to the desired value, the child pointer to the immediate left of that value is followed. If all values are less than the desired value, the rightmost child pointer is followed. Of course, the search can be terminated as soon as the desired node is found. Since the running time of the search operation depends upon the height of the tree, B-Tree-Search is O(logt n).
i <- 1while i <= n[x] and k > keyi[x] do i <- i + 1if i <= n[x] and k = keyi[x] then return (x, i)if leaf[x] then return NIL else Disk-Read(ci[x]) return B-Tree-Search(ci[x], k) |
2.3.2. B-Tree Create
The B-Tree-Create operation creates an empty b-tree by allocating a new root node that has no keys and is a leaf node. Only the root node is permitted to have these properties; all other nodes must meet the criteria outlined previously. The B-Tree-Create operation runs in time O(1).
x <- Allocate-Node()leaf[x] <- TRUEn[x] <- 0Disk-Write(x)root[T] <- x |
2.3.3. B-Tree Split-Child
If is node becomes "too full," it is necessary to perform a split operation. The split operation moves the median key of node x into its parent y where x is the ith child of y. A new node, z, is allocated, and all keys in x right of the median key are moved to z. The keys left of the median key remain in the original node x. The new node, z, becomes the child immediately to the right of the median key that was moved to the parent y, and the original node, x, becomes the child immediately to the left of the median key that was moved into the parent y.
The split operation transforms a full node with 2t - 1 keys into two nodes with t - 1 keys each. Note that one key is moved into the parent node. The B-Tree-Split-Child algorithm will run in time O(t) where t is constant.
z <- Allocate-Node()leaf[z] <- leaf[y]n[z] <- t - 1for j <- 1 to t - 1 do keyj[z] <- keyj+t[y]if not leaf[y] then for j <- 1 to t do cj[z] <- cj+t[y]n[y] <- t - 1for j <- n[x] + 1 downto i + 1 do cj+1[x] <- cj[x]ci+1 <- zfor j <- n[x] downto i do keyj+1[x] <- keyj[x]keyi[x] <- keyt[y]n[x] <- n[x] + 1Disk-Write(y)Disk-Write(z)Disk-Write(x) |
2.3.4. B-Tree Insert
r <- root[T]if n[r] = 2t - 1 then s <- Allocate-Node() root[T] <- s leaf[s] <- FALSE n[s] <- 0 c1 <- r B-Tree-Split-Child(s, 1, r) B-Tree-Insert-Nonfull(s, k) else B-Tree-Insert-Nonfull(r, k) |
2.3.5. B-Tree Insert-Nonfull
To perform an insertion on a b-tree, the appropriate node for the key must be located using an algorithm similar to B-Tree-Search. Next, the key must be inserted into the node. If the node is not full prior to the insertion, no special action is required; however, if the node is full, the node must be split to make room for the new key. Since splitting the node results in moving one key to the parent node, the parent node must not be full or another split operation is required. This process may repeat all the way up to the root and may require splitting the root node. This approach requires two passes. The first pass locates the node where the key should be inserted; the second pass performs any required splits on the ancestor nodes.
Since each access to a node may correspond to a costly disk access, it is desirable to avoid the second pass by ensuring that the parent node is never full. To accomplish this, the presented algorithm splits any full nodes encountered while descending the tree. Although this approach may result in unnecessary split operations, it guarantees that the parent never needs to be split and eliminates the need for a second pass up the tree. Since a split runs in linear time, it has little effect on the O(t logt n) running time of B-Tree-Insert.
Splitting the root node is handled as a special case since a new root must be created to contain the median key of the old root. Observe that a b-tree will grow from the top.
i <- n[x]if leaf[x] then while i >= 1 and k < keyi[x] do keyi+1[x] <- keyi[x] i <- i - 1 keyi+1[x] <- k n[x] <- n[x] + 1 Disk-Write(x) else while i >= and k < keyi[x] do i <- i - 1 i <- i + 1 Disk-Read(ci[x]) if n[ci[x]] = 2t - 1 then B-Tree-Split-Child(x, i, ci[x]) if k > keyi[x] then i <- i + 1 B-Tree-Insert-Nonfull(ci[x], k) |
For a better understanding, refer to Section 3.1, where a comprehensive example of B-Tree insertion has been elucidated.
2.3.6. B-Tree-Delete
Deletion of a key from a b-tree is possible; however, special care must be taken to ensure that the properties of a b-tree are maintained. Several cases must be considered. If the deletion reduces the number of keys in a node below the minimum degree of the tree, this violation must be corrected by combining several nodes and possibly reducing the height of the tree. If the key has children, the children must be rearranged. For a detailed discussion of deleting from a b-tree, refer to Section 3.2 and for further comprehensive understanding refer (Cormen et al. 1998, pp 395-397).
3. B-Trees Examples
3.1. B-Tree Insert
For a better understanding of B-Tree insertion operation; let's do a sequence of insertions into this B-tree (M=5, so each node other than the root must contain between 2 and 4 values):
Step 1: Insert ‘17’
Add it to the middle leaf. No overflow, so it’s done.
Step 2: Insert 6
Add it to the leftmost leaf. That overflows, so split it:
- Left = [ 2 3 ]
- Middle = 5
- Right = [ 6 7 ]
Left and Right become nodes; Middle is added to the node above with Left and Right as its children.
The node above (the root in this small example) does not overflow, so it’s done.
Step 3: Insert ‘21’
Add it to the middle leaf. That overflows, so split it:
§ left = [ 17 21 ]
§ Middle = 22
§ Right = [ 44 45 ]
Left and Right become nodes; Middle is added to the node above with Left and Right as its children.
The node above (the root in this small example) does not overflow, so it’s done.
Step 4: Insert ‘67’
Add it to the rightmost leaf. That overflows, so split it:
- Left = [ 55 66 ]
- Middle = 67
- Right = [ 68 70 ]
Left and Right become nodes; Middle is added to the node above with Left and Right as its children.
But now the node above does overflow. So it is split in exactly the same manner:
- Left = [ 5 10 ] (along with their children)
- Middle = 22
- Right = [ 50 67 ] (along with their children)
Left and Right become nodes, the children of Middle. If this were not the root, Middle would be added to the node above and the process repeated. If there is no node above, as in this example, a new root is created with Middle as its only value.
The tree-insertion algorithms previously seen add new nodes at the bottom of the tree, and then have to worry about whether doing so creates an imbalance. The B-tree insertion algorithm is just the opposite: it adds new nodes at the top of the tree (a new node is allocated only when the root splits). B-trees grow at the root, not at the leaves. Because of this, there is never any doubt that the tree is always perfectly height balanced: when a new node is added, all existing nodes become one level deeper in the tree.
3.2. B-Tree Delete
Recall the deletion algorithm for binary search trees: if the value to be deleted is in a node having two sub-trees, it would replace the value with the largest value in its left sub-tree and then delete the node in the left sub-tree that had contained the largest value (its guaranteed that this node will be easy to delete).
A similar strategy will be used to delete a value from a B-tree. If the value to be deleted does not occur in a leaf, it is replaced with the largest value in its left sub-tree and then proceeded to delete that value from the node that originally contained it. For example, if 67 is to be deleted from the above tree, the largest value in 67's left sub-tree would be founded, 66, replace 67 with 66, and then delete the occurrence of 66 in the left sub-tree. In a B-tree, the largest value in any value's left sub-tree is guaranteed to be in leaf. Therefore wherever the value to be deleted initially resides, the following deletion algorithm always begins at a leaf.
To delete value X from a B-tree, starting at a leaf node, there are 2 steps:
- Remove X from the current node. Being a leaf node there are no sub-trees to worry about.
- Removing X might cause the node containing it to have too few values. Recall that the root is required to have at least 1 value in it and all other nodes to have at least (M-1)/2 values in them. If the node has too few values, it is said to have underflowed.
If underflow does not occur, then the deletion process is finished. If it does occur, it must be fixed. The process for fixing a root is slightly different than the process for fixing the other nodes, and will be discussed afterwards.
How to fix a non-root node that has underflowed? Let us take as a specific example, deleting 6 from this B-tree (of degree 5):
Removing 6 causes the node it is in to underflow, as it now contains just 1 value (7). The strategy for fixing this is to try to `borrow' values from a neighbouring node. The current node and its more populous neighbour are joined to form a `combined node' - and in the combined node the value of the parent node should must be included that is in between these two nodes.
In this example, node [7] is joined with its more populous neighbour [17 22 44 45] and put `10' in between them, to create [6 7 10 17 22 44 45].
How many values might there be in this combined node?
§ The parent node contributes 1 value.
§ The node that underflowed contributes exactly (M-1)/2-1 values.
§ The neighbouring node contributes somewhere between (M-1)/2 and (M-1) values.
The treatment of the combined node is different depending on whether the neighbouring contributes exactly (M-1)/2 values or more than this number.
Case 1: Suppose that the neighbouring node contains more than (M-1)/2 values. In this case, the total number of values in the combined node is strictly greater than 1 + ((M-1)/2 - 1) + ((M-1)/2), i.e. it is strictly greater than (M-1). So it must contain M values or more.
The combined node is then to be split into three pieces: Left, Middle, and Right, where Middle is a single value in the very middle of the combined node. Because the combined node has M values or more, Left and Right are guaranteed to have (M-1)/2 values each, and therefore are legitimate nodes. Then value borrowed from the parent is replaced with Middle and Left and Right are used as its two children. In this case the parent's size does not change, so it is completely finished.
This is what happens in the example of deleting 6 from the tree above. The combined node [6 7 10 17 22 44 45] contains more than 3 values, so split it into:
§ Left = [ 6 7 10 ]
§ Middle = 17
§ Right = [ 22 44 45 ]
Then put Middle into the parent node (in the position where the `10' had been) with Left and Right as its children:
Case 2: Suppose, on the other hand that the neighbouring node contains exactly (M-1)/2 values. Then the total number of values in the combined node is 1 + ((M-1)/2 - 1) + ((M-1)/2) = (M-1)
In this case the combined node contains the right number of values to be treated as a node. So it is made into a node and removed from the parent node the value that has been incorporated into the new, combined node. As a concrete example of this case, suppose that, in the above tree, 3 was deleted instead of 6. The node [2 3] underflows when 3 is removed. It would be combined with its more populous neighbour [6 7] and the intervening value from the parent (5) to create the combined node [2 5 6 7]. This contains 4 values, so it can be used without further processing. The result would be:
It is very important to note that the parent node now has one fewer value. This might cause it to underflow - imagine that 5 had been the only value in the parent node. If the parent node underflows, it would be treated in exactly the same way - combined with it’s more populous neighbour etc. The underflow processing repeats at successive levels until no underflow occurs or until the root underflows (the processing for root-underflow is described next).
Now let us consider the root. For the root to underflow, it must have originally contained just one value, which now has been removed. If the root was also a leaf, then there is no problem: in this case the tree has become completely empty.
If the root is not a leaf, it must originally have had two sub-trees (because it originally contained one value). How could it possibly underflow?
The deletion process always starts at a leaf and therefore the only way the root could have its value removed is through the Case 2 processing just described: the root's two children have been combined, along with the root's only value to form a single node. But if the root's two children are now a single node, then that node can be used as the new root, and the current root (which has underflowed) can simply be deleted.
To illustrate this, suppose 7 is deleted from the following B-tree (M=5):
The node [3 7] would underflow, and the combined node [3 10 18 20] would be created. This has 4 values, which is acceptable when M=5. So it would be kept as a node, and `10' would be removed from the parent node - the root. This is the only circumstance in which underflow can occur in a root that is not a leaf. The situation is this:
Clearly, the current root node, now empty, can be deleted and its child used as the new root.
4. Implementing B-Trees
The following contains a class template for elements stored in a B-tree, and a class for a B-tree node, which provides all the methods needed to search, insert, or delete. a sample "main" function is also provided to show how to use the B-tree.
To understand the identifiers and comments, visualize the tree as having its root node at the top of the diagram, its leaf nodes at the bottom of the diagram, and each node as containing an array oriented horizontally, with the smallest element on the left and the largest element on the right.
The zeroth element of a node contains only a sub-tree pointer, no key value or payload.
A b-tree grows "upward", by splitting the root node when the node's capacity is exceeded. Conversely, the depth of the tree is always reduced by merging the last remaining element of the root node with the elements of its two child nodes, so the tree contracts "from the top".
class BTree : public MWayTree{ BTree* parent; void InsertPair (Object&, BTree&); void AttachKey (unsigned int, Object&); void AttachSubtree (unsigned int, MWayTree&); Object& InsertKey (unsigned int, Object&); BTree& InsertSubtree (unsigned int, BTree&); void AttachLeftHalfOf (BTree const&); void AttachRightHalfOf (BTree const&, Object&, BTree&);public: BTree (unsigned int); BTree (unsigned int, BTree&); void Insert (Object&); void Withdraw (Object&);}; |
void BTree::Insert (Object& object){ if (IsEmpty ()) { if (parent == 0) { AttachSubtree (0, *new BTree (m, *this)); AttachKey (1, object); AttachSubtree (1, *new BTree (m, *this)); numberOfKeys = 1; } else parent->InsertPair (object, *new BTree (m, *parent)); } else { unsigned int const index = FindIndex (object); if (index != 0 && object == *key [index]) throw invalid_argument ("duplicate key"); subtree [index]->Insert (object); }} |
void BTree::InsertPair (Object& object, BTree& child){ unsigned int const index = FindIndex (object); BTree& extraTree = InsertSubtree (index + 1, child); Object& extraKey = InsertKey (index + 1, object); if (++numberOfKeys == m) { if (parent == 0) { BTree& left = *new BTree (m, *this); BTree& right = *new BTree (m, *this); left.AttachLeftHalfOf (*this); right.AttachRightHalfOf (*this, extraKey, extraTree); AttachSubtree (0, left); AttachKey (1, *key [(m + 1)/2]); AttachSubtree (1, right); numberOfKeys = 1; } else { numberOfKeys = (m + 1)/2 - 1; BTree& right = *new BTree (m, *parent); right.AttachRightHalfOf (*this, extraKey, extraTree); parent->InsertPair (*key [(m + 1)/2], right); } }} |
For a complete implementation of B-Trees refer to Texteclectric, 2003.
5. Application of B-Trees
5.1. Databases
A database is a collection of data organized in a fashion that facilitates updating, retrieving, and managing the data. The data can consist of anything, including, but not limited to names, addresses, pictures, and numbers. Databases are commonplace and are used everyday. For example, an airline reservation system might maintain a database of available flights, customers, and tickets issued. A teacher might maintain a database of student names and grades.
Because computers excel at quickly and accurately manipulating, storing, and retrieving data, databases are often maintained electronically using a database management system. Database management systems are essential components of many everyday business operations. Database products like Microsoft SQL Server, Sybase Adaptive Server, IBM DB2, and Oracle serve as a foundation for accounting systems, inventory systems, medical recordkeeping systems, airline reservation systems, and countless other important aspects of modern businesses.
It is not uncommon for a database to contain millions of records requiring many gigabytes of storage. For examples, TELSTRA, an Australian telecommunications company, maintains a customer billing database with 51 billion rows (yes, billion) and 4.2 terabytes of data. In order for a database to be useful and usable, it must support the desired operations, such as retrieval and storage, quickly. Because databases cannot typically be maintained entirely in memory, b-trees are often used to index the data and to provide fast access. For example, searching an un-indexed and unsorted database containing n key values will have a worst case running time of O(n); if the same data is indexed with a b-tree, the same search operation will run in O(log n). To perform a search for a single key on a set of one million keys (1,000,000), a linear search will require at most 1,000,000 comparisons. If the same data is indexed with a b-tree of minimum degree 10, 114 comparisons will be required in the worst case. Clearly, indexing large amounts of data can significantly improve search performance. Although other balanced tree structures can be used, a b-tree also optimizes costly disk accesses that are of concern when dealing with large data sets.
5.2. Concurrent Access to B-Trees
Databases typically run in multi-user environments where many users can concurrently perform operations on the database. Unfortunately, this common scenario introduces complications. For example, imagine a database storing bank account balances. Now assume that someone attempts to withdraw $40 from an account containing $60. First, the current balance is checked to ensure sufficient funds. After funds are disbursed, the balance of the account is reduced. This approach works flawlessly until concurrent transactions are considered. Suppose that another person simultaneously attempts to withdraw $30 from the same account. At the same time the account balance is checked by the first person, the account balance is also retrieved for the second person. Since neither person is requesting more funds than are currently available, both requests are satisfied for a total of $70. After the first person's transaction, $20 should remain ($60 - $40), so the new balance is recorded as $20. Next, the account balance after the second person's transaction, $30 ($60 - $30), is recorded overwriting the $20 balance. Unfortunately, $70 has been disbursed, but the account balance has only been decreased by $30. Clearly, this behaviour is undesirable, and special precautions must be taken.
A b-tree suffers from similar problems in a multi-user environment. If two or more processes are manipulating the same tree, it is possible for the tree to become corrupt and result in data loss or errors.
The simplest solution is to serialize access to the data structure. In other words, if another process is using the tree, all other processes must wait. Although this is feasible in many cases, it can place an unnecessary and costly limit on performance because many operations actually can be performed concurrently without risk. Locking, introduced by Gray and refined by many others, provides a mechanism for controlling concurrent operations on data structures in order to prevent undesirable side effects and to ensure consistency.
6. Variants of B-Trees
6.1. B+-Trees
- Internal nodes contain the indices to the records corresponding to the key values k1, k2,..., km stored at the internal node. This obviates the need for repeating these key values and associated indices at the leaf level.
- More efficient than B-Trees in the case of successful searches.
6.2. B*-Trees
§ The minimum number of children at each internal node (except the root) is
§ Path lengths are smaller for obvious reasons.
§ Insertions and deletions are more complex.
6.3. Trade offs
- B-trees have faster lookup than B+ trees.
- In B-tree, non-leaf & leaf are of different sizes.
- In B-tree, deletion is more complicated
The traditional implementation for a B-tree uses many pointers (more than one per key), and which can directly affect the performance of the B-tree. So, conclusively, B+ trees are preferred!
7. Conclusion
The B-tree is probably the most popular method in use today for indexes and inverted files in database management systems. B-Trees are often described as a good way to store and retrieve data, especially to and from disk. They're efficient to use and easy to program, and they're often mentioned but not so often discussed. They show up all over the place: In the Berkeley DB_File package, which is (semi-) standard with Perl, and in large high-performance databases. For example, B-Trees are the technology that underlying IBM's well-known VSAM files.
The most important point about B-Trees is that it's easy to implement a version that saves the tree on disk. The tree nodes never need to grow or shrink, so one never has the problem of having to move one to a different place in the file when you insert a key. For this reason, they are frequently used for disk databases where the data have to be accessed by key.
When used in DBM files, B-trees have another big advantage over binary trees - even balanced binary trees. The binary search that occurs in a B-tree node takes about the same amount of CPU time as the binary search on the nodes of a binary tree with the sane number of keys. But when the tree lives on disk, each node must be loaded into memory before it can be examined. In a B-tree, one can adjust B so that each entire node can be loaded with exactly one disk operation, and then searched quickly in memory. In a binary tree, each key resides in its own node, which must be loaded from disk separately. A binary tree therefore typically requires between B/2 and B times as many disk accesses as a B-tree of similar size, because it has fewer keys per node. When the tree lives on the disk, the time to search the tree is dominated by the disk access time, and B-trees are therefore much faster than even balanced binary trees.
DBM files are almost invariably implemented with either B-trees or with hash tables. (Hash tables are the method that Perl uses for regular in-memory hash variables.) However, B-Trees present one enormous advantage over hash tables: The keys are stored in sorted order. Why is this important? Suppose one has a range, and one wants to retrieve all the data for all the keys in that range. One can do this efficiently if the database is stored using B-trees: Locate the two keys corresponding to the upper and lower bounds of the range, and then take all the keys in between. With hash tables, the keys are not stored in any particular order, so there is no "in between," and to retrieve a range of them, you must retrieve all the keys, extract the ones one want, sort them into order, and then query the hash once for each key. That's vastly less efficient.
B-trees have substantial advantages over alternative implementations when node access times far exceed access times within nodes. This usually occurs when most nodes are in secondary storage such as hard drives. By maximizing the number of child nodes within each internal node, the height of the tree decreases, balancing occurs less often, and efficiency increases. Usually this value is set such that each node takes up a full disk block or an analogous size in secondary storage.
Bibliography
[Bayer, 1972]
Bayer, R. Symmetric binary B-trees: Data Structures and maintenance algorithms. Acta Informatica, Volume 1, pp.290-306, 1972.
[Bayer et al, 1972]
Bayer, R and McCreight, E.M. Organization and maintenance of large ordered indexes. Acta Informatica, Volume 1, Number 3, pp. 173-189, 1972.
[Comer, 1979]
Comer, D. The ubiquitous B-tree. ACM Computing Surveys, Volume 11, Number 2, pp 121-137, 1979.
[Cormen et al, 1998]
Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, MIT Press, Massachusetts: 1998.
[Kruse, 1987]
Kruse, Robert L. Data Structures & Program Design Second Edition, Prentice-Hall, 1987.
[Kruse et al, 1999]
Kruse, Robert L & Ryba, Alexander J. Data Structures and Program Design in C++, Third Edition, Prentice Hall, 1999.
[Maire, 1998]
Maire, Frederic. (October 18, 1998) An Introduction to B-Trees
http://sky.fit.qut.edu.au/~maire/baobab/lecture/
[Preiss, 1998]
Preiss, Bruno R. (1998) Data Structures and Algorithms with Object-Oriented Design Patterns in Java.
http://www.brpreiss.com/books/opus5/html/page339.html
[Shaffer, 1997]
Shaffer, Clifford A. A Practical Introduction to Data Structures and Algorithm Analysis, Prentice-Hall (1997).
[Tenenbaum et al, 1986]
Tenenbaum, Aaron M. & Augenstein, Moshe J. Data Structures using Pascal. Second Edition, Prentice Hall, 1986.
[Textelectric, 2003]
Texteclectric. (May 9, 2003) Implemeting B-Trees.
http://textelectric.net/btree.html
0 comments:
Post a Comment