The B-Tree IndexOutlineIntroductionPowerPoint PresentationThe B-Tree ShapeSlide 6The Problem of Unbalanced TreesDisadvantage of unbalanced treeUnbalanced Tree (cont.)Slide 10The B-Tree Shape (c.)Slide 12B-TreesB-Trees - DefinitionSlide 15Slide 16B-tree of order nSlide 18Other definitionA B-tree of order 2Dynamic changes in the B-TreeProperties of the B-TreeProperties of the B-Tree (c.)Insertion in B-TreeInsertion (cont.)Slide 26Inserting into a B-TreeInserting into a B-Tree: Splitting a NodeInsert 19,12, 22,15.InsertionSlide 31SearchingSearching (cont.)Deletion form a B-TreeDeletion (cont.)Slide 36Slide 37Deleting from a B-TreeDeleting from a B-Tree (continued)Slide 40Delete 18Delete 5Delete 19Delete 12Properties of B-TreesAdvantages of B-treeORACLE Create Index StatementORACLE Create Index Statement (c.)DB2 Create Index StatementDB2 Create Index Statement (c.)INGRES Create Index StatementINGRES Create Index Statement (c.)Index Node Layout and Free SpaceMore about the B-TreeMore about the B-Tree (c.)SummaryThe B-Tree IndexThe B-Tree IndexProf. Sin-Min LeeDepartment of Computer ScienceSan Jose State UniversityOutline•Introduction•The B-tree shape•Dynamic changes in the B-tree•Properties of the B-tree•Create index statement syntax•More about the B-tree•SummaryIntroduction•A B-tree is a keyed index structure, comparable to a number of memory resident keyed lookup structures such as balanced binary tree, the AVL tree, and the 2-3 tree.•The difference is that a B-tree is meant to reside on disk, being made partially memory-resident only when entries int the structure are accessed.•The B-tree structure is the most common used index type in databases today.•It is provided by ORACLE, DB2, and INGRES.The B-Tree Shape•A B-tree is built upside down with the root at the top and the leaves at the bottom.•All nodes above the leaf level, including the root, are called directory nodes or index nodes.•Directory nodes below the root are called internal nodes.•The root node is known as level 1 of the B-tree and successively lower levels are given successively larger level numbers with the leaf nodes at the lowest level.•The total number of levels is called the depth of the B-tree.•Balanced and Unbalanced Trees•Trees can be balanced or unbalanced. •In a balanced tree, every path from the route to a leaf node is the same length. •A tree that is balanced has at most logorder n levels. This is desirable for an index.The Problem of Unbalanced Trees •a. A Troublesome Search Tree•b. A More Troublesome Search Tree12534697854321Disadvantage of unbalanced tree•Searching an unbalanced tree may require traversing an arbitrary and unpredictable number of nodes and pointers.Unbalanced Tree (cont.)Problems: 1. The levels of the tree are only sparsely filled 2. Resulting in long 3. Deep paths and defeating the purpose of binary trees in the first place.The general name for B-trees is multiway trees. However, the best known of them have their very own names: 2-3 trees, B* trees, and B+ trees. Here we will look only at 2-3 trees. They are the simplest. And or purposes of learning the underlying principles this is good. Multiway trees can get pretty complicated pretty fast. Keep in mind that 2-3 trees as we study them are rarely built. Their larger cousins, B* and B+ trees are often used for medium and large database applications. The general idea of a multiway tree of order n is that each node can hold up to n - 1 key values and each node can have up to n childern. So, a 2-3 tree is actually a multiway tree of order 3. That means that a 2-3 tree has nodes that can hold 1 or 2 values and that a node can have 0, 1, 2, or 3 children. Thus the name 2-3 treeThe B-Tree Shape (c.)level1: root node, level2: directory nodes, level3: leaf nodesB-Trees•For a binary search tree, the search time is O(h), where h is the height of the tree. • The height cannot be less than roughly log2n for a tree with n nodes. •If the tree is too large for internal memory, each access of a node is an I/O. •For a tree with 10,000 nodes: • log210000 = 100 disk accesses • We need a structure that would require only 3 or 4 disk accesses.B-Trees - Definition• A B-tree of order M is an M-ary tree with the following properties: • (1) The data items are stored at leaves. • (2) The nonleaf nodes store up to M - 1 keys to guide the searching; key i represents the smallest key in subtree i + 1.•(3) The root is either a leaf or has between 2 and M children. • (4) All nonleaf nodes (except the root) have between ceiling(M/2) and M children. • (5) All leaves are at the same depth and have between ceiling(L/2) and L data items, for some L.B-tree of order n•Every B-tree is of some "order n", meaning nodes contain from n to 2n keys (so nodes are always at least half full of keys), and n+1 to 2n+1 pointers, and n can be any number. •Keys are kept in sorted order within each node. A corresponding list of pointers are effectively interspersed between keys to indicate where to search for a key if it isn't in the current node.•A B-tree of order n is a multi-way search tree with two properties: • 1.All leaves are at the same level • 2.The number of keys in any node lies between n and 2n, with the possible exception of the root which may have fewer keys.Other definitionA B-tree of order m is a m-way tree that satisfies the following conditions. • Every node has < m children. • Every internal node (except the root) has <m/2 children. • The root has >2 children. • An internal node with k children contains (k-1) ordered keys. The leftmost child contains keys less than or equal to the first key in the node. The second child contains keys greater than the first keys but less than or equal to the second key, and so on.A B-tree of order 2Dynamic changes in the B-Tree•A B-tree is an efficient self-modifying structure when new entries are inserted pointing to new rows inserted in the indexed table.•The nodes at every level are generally assumed not to be full.•Space is left so that inserts are often possible to a node at any level without new disk space being required.•An insert of a new entry always occurs at the leaf level, but occasionally the leaf node is too full to simply accept the new entry. In this case, for additional space the leaf level node is split into two leaf pages.Properties of the B-TreeAssumptions:•Entry key values
View Full Document
Unlocking...