Cơ sở dữ liệu - Chapter 12: Indexing and hashing

Database System Concepts, 5th Ed. ©Silberschatz, Korth and Sudarshan See www.db­book.com for conditions on re­use  Chapter 12: Indexing and Hashing Rev. Sep 17, 2008 ©Silberschatz, Korth and Sudarshan12.2Database System Concepts ­ 5th Edition. Chapter 12:  Indexing and Hashing n Basic Concepts n Ordered Indices  n B+­Tree Index Files n B­Tree Index Files n Static Hashing n Dynamic Hashing  n Comparison of Ordered Indexing and Hashing  n Index Definition in SQL n Multiple­Key Access ©Silberschatz, Korth and Sudarshan12.3Database System Concepts ­ 5th Edition. Basic Concepts n Indexing mechanisms used to speed up access to desired  data. l E.g., author catalog in library n Search Key ­ attribute to set of attributes used to look up  records in a file. n An index file consists of records (called index entries) of the  form n Index files are typically much smaller than the original file  n Two basic kinds of indices: l Ordered indices:  search keys are stored in sorted order l Hash indices:  search keys are distributed uniformly across  “buckets” using a “hash function”.  search­key pointer ©Silberschatz, Korth and Sudarshan12.4Database System Concepts ­ 5th Edition. Index Evaluation Metrics n Access types supported efficiently.  E.g.,  l records with a specified value in the attribute l or records with an attribute value falling in a specified range  of values (e.g.  10000 < salary < 40000) n Access time n Insertion time n Deletion time n Space overhead ©Silberschatz, Korth and Sudarshan12.5Database System Concepts ­ 5th Edition. Ordered Indices n In an ordered index, index entries are stored sorted on the  search key value.  E.g., author catalog in library. n Primary index: in a sequentially ordered file, the index whose  search key specifies the sequential order of the file. l Also called clustering index l The search key of a primary index is usually but not  necessarily the primary key. n Secondary index: an index whose search key specifies an  order different from the sequential order of the file.  Also called  non­clustering index. n Index­sequential file: ordered sequential file with a primary  index. ©Silberschatz, Korth and Sudarshan12.6Database System Concepts ­ 5th Edition. Dense Index Files n Dense index — Index record appears for every search­key  value in the file.  ©Silberschatz, Korth and Sudarshan12.7Database System Concepts ­ 5th Edition. Sparse Index Files n Sparse Index:  contains index records for only some search­key values. l Applicable when records are sequentially ordered on search­key n To locate a record with search­key value K we: l Find index record with largest search­key value < K l Search file sequentially starting at the record to which the index  record points ©Silberschatz, Korth and Sudarshan12.8Database System Concepts ­ 5th Edition. Sparse Index Files (Cont.) n Compared to dense indices: l Less space and less maintenance overhead for insertions and  deletions. l Generally slower than dense index for locating records. n Good tradeoff: sparse index with an index entry for every block in  file, corresponding to least search­key value in the block. ©Silberschatz, Korth and Sudarshan12.9Database System Concepts ­ 5th Edition. Multilevel Index n If primary index does not fit in memory, access becomes  expensive. n Solution: treat primary index kept on disk as a sequential file  and construct a sparse index on it. l outer index – a sparse index of primary index l inner index – the primary index file n If even outer index is too large to fit in main memory, yet  another level of index can be created, and so on. n Indices at all levels must be updated on insertion or deletion  from the file. ©Silberschatz, Korth and Sudarshan12.10Database System Concepts ­ 5th Edition. Multilevel Index (Cont.) ©Silberschatz, Korth and Sudarshan12.11Database System Concepts ­ 5th Edition. Index Update:  Record Deletion n If deleted record was the only record in the file with its particular search­ key value, the search­key is deleted from the index also. n Single­level index deletion: l Dense indices – deletion of search­key: similar to file record deletion. l Sparse indices –   if deleted key value exists in the index, the value is replaced by  the next search­key value in the file (in search­key order).    If the next search­key value already has an index entry, the entry  is deleted instead of being replaced. ©Silberschatz, Korth and Sudarshan12.12Database System Concepts ­ 5th Edition. Index Update: Record Insertion n Single­level index insertion: l Perform a lookup using the key value from inserted record l Dense indices – if the search­key value does not appear in  the index, insert it. l Sparse indices – if index stores an entry for each block of  the file, no change needs to be made to the index unless a  new block is created.    If a new block is created, the first search­key value  appearing in the new block is inserted into the index. n Multilevel insertion (as well as deletion) algorithms are simple  extensions of the single­level algorithms ©Silberschatz, Korth and Sudarshan12.13Database System Concepts ­ 5th Edition. Secondary Indices Example n Index record points to a bucket that contains pointers to all the  actual records with that particular search­key value. n Secondary indices have to be dense Secondary index on balance field of account ©Silberschatz, Korth and Sudarshan12.14Database System Concepts ­ 5th Edition. Primary and Secondary Indices n Indices offer substantial benefits when searching for records. n BUT: Updating indices imposes overhead on database  modification ­­when a file is modified, every index on the file  must be updated,  n Sequential scan using primary index is efficient, but a  sequential scan using a secondary index is expensive  l Each record access may fetch a new block from disk l Block fetch requires about 5 to 10 micro seconds, versus  about 100 nanoseconds for memory access ©Silberschatz, Korth and Sudarshan12.15Database System Concepts ­ 5th Edition. B+­Tree Index Files n Disadvantage of indexed­sequential files l performance degrades as file grows, since many overflow  blocks get created.   l Periodic reorganization of entire file is required. n Advantage of B+­tree index files:   l automatically reorganizes itself with small, local, changes,  in the face of insertions and deletions.   l Reorganization of entire file is not required to maintain  performance. n (Minor) disadvantage of B+­trees:  l extra insertion and deletion overhead, space overhead. n Advantages of B+­trees outweigh disadvantages l B+­trees are used extensively B+­tree indices are an alternative to indexed­sequential files. ©Silberschatz, Korth and Sudarshan12.16Database System Concepts ­ 5th Edition. B+­Tree Index Files (Cont.) n All paths from root to leaf are of the same length n Each node that is not a root or a leaf has between n/2 and n  children. n A leaf node has between  (n–1)/2  and n–1 values n Special cases:  l If the root is not a leaf, it has at least 2 children. l If the root is a leaf (that is, there are no other nodes in the  tree), it can have between 0 and (n–1) values. A B+­tree is a rooted tree satisfying the following properties: ©Silberschatz, Korth and Sudarshan12.17Database System Concepts ­ 5th Edition. B+­Tree Node Structure n Typical node l Ki are the search­key values  l Pi are pointers to children (for non­leaf nodes) or pointers to  records or buckets of records (for leaf nodes). n The search­keys in a node are ordered   K1 < K2 < K3 < . . . < Kn–1 ©Silberschatz, Korth and Sudarshan12.18Database System Concepts ­ 5th Edition. Leaf Nodes in B+­Trees n For i = 1, 2, . . ., n–1, pointer Pi either points to a file record with  search­key value Ki, or to a bucket of pointers to file records,  each record having search­key value Ki.  Only need bucket  structure if search­key does not form a primary key. n If Li, Lj are leaf nodes and i < j, Li’s search­key values are less  than Lj’s search­key values n Pn points to next leaf node in search­key order Properties of a leaf node: ©Silberschatz, Korth and Sudarshan12.19Database System Concepts ­ 5th Edition. Non­Leaf Nodes in B+­Trees n Non leaf nodes form a multi­level sparse index on the leaf  nodes.  For a non­leaf node with m pointers: l All the search­keys in the subtree to which P1 points are  less than K1 l For 2 ≤  i ≤  n – 1, all the search­keys in the subtree to  which Pi points have values greater than or equal to Ki–1  and less than Ki l All the search­keys in the subtree to which Pn points have  values greater than or equal to Kn–1 ©Silberschatz, Korth and Sudarshan12.20Database System Concepts ­ 5th Edition. Example of a B+­tree B+­tree for account file (n = 3) ©Silberschatz, Korth and Sudarshan12.21Database System Concepts ­ 5th Edition. Example of B+­tree n Leaf nodes must have between 2 and 4 values  ( (n–1)/2  and n –1, with n = 5). n Non­leaf nodes other than root must have between 3  and 5 children ( (n/2  and n with n =5). n Root must have at least 2 children. B+­tree for account file (n = 5) ©Silberschatz, Korth and Sudarshan12.22Database System Concepts ­ 5th Edition. Observations about B+­trees n Since the inter­node connections are done by pointers,  “logically” close blocks need not be “physically” close. n The non­leaf levels of the B+­tree form a hierarchy of sparse  indices. n The B+­tree contains a relatively small number of levels  Level below root has at least 2*  n/2  values  Next level has at least 2*  n/2  *  n/2  values  .. etc. l If there are K search­key values in the file, the tree height is  no more than   logn/2(K) l thus searches can be conducted efficiently. n Insertions and deletions to the main file can be handled  efficiently, as the index can be restructured in logarithmic time  (as we shall see). ©Silberschatz, Korth and Sudarshan12.23Database System Concepts ­ 5th Edition. Queries on B+­Trees n Find all records with a search­key value of k. H N=root H Repeat 4 Examine N for the smallest search­key value > k. 4 If such a value exists, assume it is Ki.  Then set N = Pi 4 Otherwise k ≥  Kn–1. Set N = Pn  Until N is a leaf node H If for some i, key Ki = k  follow pointer Pi  to the desired record or bucket.   H Else no record with search­key value k exists. ©Silberschatz, Korth and Sudarshan12.24Database System Concepts ­ 5th Edition. Queries on B+­Trees (Cont.) n If there are K search­key values in the file, the height of the  tree is no more than  log n/2 (K) . n A node is generally the same size as a disk block, typically 4  kilobytes l and n is typically around 100 (40 bytes per index entry). n With 1 million search key values and n = 100 l at most  log50(1,000,000) = 4 nodes are accessed in a  lookup. n Contrast this with a balanced binary tree with 1 million search  key values — around 20 nodes are accessed in a lookup l above difference is significant since every node access  may need a disk I/O, costing around 20 milliseconds ©Silberschatz, Korth and Sudarshan12.25Database System Concepts ­ 5th Edition. Updates on B+­Trees:  Insertion 1. Find the leaf node in which the search­key value would appear 2. If the search­key value is already present in the leaf node n Add record to the file 3. If the search­key value is not present, then  1. add the record to the main file (and create a bucket if  necessary) 2. If there is room in the leaf node, insert (key­value, pointer)  pair in the leaf node 3. Otherwise, split the node (along with the new (key­value,  pointer) entry) as discussed in the next slide. ©Silberschatz, Korth and Sudarshan12.26Database System Concepts ­ 5th Edition. Updates on B+­Trees:  Insertion (Cont.) n Splitting a leaf node: l take the n (search­key value, pointer) pairs (including the one  being inserted) in sorted order.  Place the first n/2 in the original  node, and the rest in a new node. l let the new node be p, and let k be the least key value in p.  Insert  (k,p) in the parent of the node being split.  l If the parent is full, split it and propagate the split further up. n Splitting of nodes proceeds upwards till a node that is not full is found.  l In the worst case the root node may be split increasing the height  of the tree by 1.  Result of splitting node containing Brighton and Downtown on inserting  Clearview Next step: insert entry with (Downtown,pointer­to­new­node) into parent ©Silberschatz, Korth and Sudarshan12.27Database System Concepts ­ 5th Edition. Updates on B+­Trees:  Insertion (Cont.) B+­Tree before and after insertion of “Clearview” ©Silberschatz, Korth and Sudarshan12.28Database System Concepts ­ 5th Edition. Redwood Insertion in B+­Trees (Cont.) n Splitting a non­leaf node: when inserting (k,p) into an already  full internal node N l Copy N to an in­memory area M with space for n+1  pointers and n keys l Insert (k,p) into M l Copy P1,K1, , K  n/2 ­1,P  n/2  from M back into node N l Copy P n/2 +1,K  n/2 +1,,Kn,Pn+1 from M into newly  allocated node N’ l Insert (K  n/2 ,N’) into parent N n Read pseudocode in book! Downtown  Mianus  Perryridge Downtown  Mianus      ©Silberschatz, Korth and Sudarshan12.29Database System Concepts ­ 5th Edition. Updates on B+­Trees: Deletion n Find the record to be deleted, and remove it from the main file  and from the bucket (if present) n Remove (search­key value, pointer) from the leaf node if there  is no bucket or if the bucket has become empty n If the node has too few entries due to the removal, and the  entries in the node and a sibling fit into a single node, then  merge siblings: l Insert all the search­key values in the two nodes into a  single node (the one on the left), and delete the other node. l Delete the pair (Ki–1, Pi), where Pi is the pointer to the  deleted node, from its parent, recursively using the above  procedure. ©Silberschatz, Korth and Sudarshan12.30Database System Concepts ­ 5th Edition. Updates on B+­Trees:  Deletion n Otherwise, if the node has too few entries due to the removal,  but the entries in the node and a sibling do not fit into a single  node, then redistribute pointers: l Redistribute the pointers between the node and a sibling  such that both have more than the minimum number of  entries. l Update the corresponding search­key value in the parent of  the node. n The node deletions may cascade upwards till a node which has    n/2  or more pointers is found.   n If the root node has only one pointer after deletion, it is deleted  and the sole child becomes the root.  ©Silberschatz, Korth and Sudarshan12.31Database System Concepts ­ 5th Edition. Examples of B+­Tree Deletion n Deleting “Downtown” causes merging of under­full leaves l  leaf node can become empty only for n=3! Before and after deleting “Downtown” ©Silberschatz, Korth and Sudarshan12.32Database System Concepts ­ 5th Edition. Examples of B+­Tree Deletion (Cont.) Before and After deletion of “Perryridge” from result of  previous example ©Silberschatz, Korth and Sudarshan12.33Database System Concepts ­ 5th Edition. Examples of B+­Tree Deletion (Cont.) n Leaf with “Perryridge” becomes underfull (actually empty, in this  special case) and merged with its sibling. n As a result “Perryridge” node’s parent became underfull, and was  merged with its sibling  l Value separating two nodes (at parent) moves into merged node l Entry deleted from parent n Root node then has only one child, and is deleted ©Silberschatz, Korth and Sudarshan12.34Database System Concepts ­ 5th Edition. Example of B+­tree Deletion (Cont.) n Parent  of leaf containing Perryridge became underfull, and borrowed a  pointer from its left sibling n Search­key value in the parent’s parent changes as a result Before and after deletion of “Perryridge” from earlier example ©Silberschatz, Korth and Sudarshan12.35Database System Concepts ­ 5th Edition. B+­Tree File Organization n Index file degradation problem is solved by using B+­Tree indices. n Data file degradation problem is solved by using B+­Tree File  Organization. n The leaf nodes in a B+­tree file organization store records, instead  of pointers. n Leaf nodes are still required to be half full l Since records are larger than pointers, the maximum number  of records that can be stored in a leaf node is less than the  number of pointers in a nonleaf node. n Insertion and deletion are handled in the same way as insertion  and deletion of entries in a B+­tree index. ©Silberschatz, Korth and Sudarshan12.36Database System Concepts ­ 5th Edition. B+­Tree File Organization (Cont.) n Good space utilization important since records use more space than  pointers.   n To improve space utilization, involve more sibling nodes in  redistribution during splits and merges l Involving 2 siblings in redistribution (to avoid split / merge where  possible) results in each node having at least              entries Example of B+­tree File Organization  3/2n ©Silberschatz, Korth and Sudarshan12.37Database System Concepts ­ 5th Edition. Indexing Strings n Variable length strings as keys l Variable fanout l Use space utilization as criterion for splitting, not number of  pointers n Prefix compression l Key values at internal nodes can be prefixes of full key  Keep enough characters to distinguish entries in the  subtrees separated by the key value – E.g. “Silas” and “Silberschatz” can be separated by  “Silb” l Keys in leaf node can be compressed by sharing common  prefixes ©Silberschatz, Korth and Sudarshan12.38Database System Concepts ­ 5th Edition. B­Tree Index Files n Similar to B+­tree, but B­tree allows search­key values  to appear only once; eliminates redundant storage of  search keys. n Search keys in nonleaf nodes appear nowhere else in  the B­tree; an additional pointer field for each search  key in a nonleaf node must be included. n Generalized B­tree leaf node n Nonleaf node – pointers Bi are the bucket or file record  pointers. ©Silberschatz, Korth and Sudarshan12.39Database System Concepts ­ 5th Edition. B­Tree Index File Example B­tree (above) and B+­tree (below) on same data ©Silberschatz, Korth and Sudarshan12.40Database System Concepts ­ 5th Edition. B­Tree Index Files (Cont.) n Advantages of B­Tree indices: l May use less tree nodes than a corresponding B+­Tree. l Sometimes possible to find search­key value before reaching  leaf node. n Disadvantages of B­Tree indices: l Only small fraction of all search­key values are found early  l Non­leaf nodes are larger, so fan­out is reduced.  Thus, B­ Trees typically have greater depth than corresponding B+­Tree l Insertion and deletion more complicated than in B+­Trees  l Implementation is harder than B+­Trees. n Typically, advantages of B­Trees do not out weigh disadvantages.  ©Silberschatz, Korth and Sudarshan12.41Database System Concepts ­ 5th Edition. Multiple­Key Access n Use multiple indices for certain types of queries. n Example:  select account_number from account where branch_name = “Perryridge” and  balance = 1000 n Possible strategies for processing query using indices on single  attributes: 1. Use index on branch_name to find accounts with branch  name Perryridge; test balance = 1000  2. Use index on balance to find accounts with balances of  $1000; test branch_name = “Perryridge”. 3. Use branch_name index to find pointers to all records  pertaining to the Perryridge branch.  Similarly use index on  balance.  Take intersection of both sets of pointers obtained. ©Silberschatz, Korth and Sudarshan12.42Database System Concepts ­ 5th Edition. Indices on Multiple Keys n Composite search keys are search keys containing more  than one attribute l E.g. (branch_name, balance) n Lexicographic ordering: (a1, a2) < (b1, b2) if either  l a1 < b1, or  l a1=b1 and  a2 < b2 ©Silberschatz, Korth and Sudarshan12.43Database System Concepts ­ 5th Edition. Indices on Multiple Attributes n  For           where branch_name = “Perryridge” and balance = 1000 the index on (branch_name, balance) can be used to fetch only  records that satisfy both conditions. l Using separate indices in less efficient — we may fetch  many records (or pointers) that satisfy only one of the  conditions. n Can also efficiently handle             where branch_name = “Perryridge” and balance < 1000 n But cannot efficiently handle           where branch_name < “Perryridge” and balance = 1000 l May fetch many records that satisfy the first but not the  second condition Suppose we have an index on combined search­key (branch_name, balance). ©Silberschatz, Korth and Sudarshan12.44Database System Concepts ­ 5th Edition. Non­Unique Search Keys n Alternatives: l Buckets on separate block (bad idea) l List of tuple pointers with each key  Low space overhead, no extra cost for queries  Extra code to handle read/update of long lists  Deletion of a tuple can be expensive if there are many  duplicates on search key (why?) l Make search key unique by adding a record­identifier  Extra storage overhead for keys  Simpler code for insertion/deletion  Widely used ©Silberschatz, Korth and Sudarshan12.45Database System Concepts ­ 5th Edition. Other Issues in Indexing n Covering indices l Add extra attributes to index so (some) queries can avoid  fetching the actual records  Particularly useful for secondary indices  – Why? l Can store extra attributes only at leaf n Record relocation and secondary indices l If a record moves, all secondary indices that store record  pointers have to be updated  l Node splits in B+­tree file organizations become very expensive l Solution: use primary­index search key instead of record  pointer in secondary index  Extra traversal of primary index to locate record – Higher cost for queries, but node splits are cheap  Add record­id if primary­index search key is non­unique Database System Concepts, 5th Ed. ©Silberschatz, Korth and Sudarshan See www.db­book.com for conditions on re­use  Hashing ©Silberschatz, Korth and Sudarshan12.47Database System Concepts ­ 5th Edition. Static Hashing n A bucket is a unit of storage containing one or more records (a  bucket is typically a disk block).  n In a hash file organization we obtain the bucket of a record directly  from its search­key value using a hash function. n Hash function h is a function from the set of all search­key values K  to the set of all bucket addresses B. n Hash function is used to locate records for access, insertion as well  as deletion. n Records with different search­key values may be mapped to the  same bucket; thus entire bucket has to be searched sequentially to  locate a record.  ©Silberschatz, Korth and Sudarshan12.48Database System Concepts ­ 5th Edition. Example of Hash File Organization n There are 10 buckets, n The binary representation of the ith character is assumed to be the  integer i. n The hash function returns the sum of the binary representations of  the characters modulo 10 l E.g. h(Perryridge) = 5    h(Round Hill) = 3   h(Brighton) = 3 Hash file organization of account file, using branch_name as key  (See figure in next slide.) ©Silberschatz, Korth and Sudarshan12.49Database System Concepts ­ 5th Edition. Example of Hash File Organization  Hash file organization  of account file, using  branch_name as key (see previous slide for  details). ©Silberschatz, Korth and Sudarshan12.50Database System Concepts ­ 5th Edition. Hash Functions n Worst hash function maps all search­key values to the same bucket;  this makes access time proportional to the number of search­key values  in the file. n An ideal hash function is uniform, i.e., each bucket is assigned the  same number of search­key values from the set of all possible values. n Ideal hash function is random, so each bucket will have the same  number of records assigned to it irrespective of the actual distribution of  search­key values in the file. n Typical hash functions perform computation on the internal binary  representation of the search­key.  l For example, for a string search­key, the binary representations of  all the characters in the string could be added and the sum modulo  the number of buckets could be returned. . ©Silberschatz, Korth and Sudarshan12.51Database System Concepts ­ 5th Edition. Handling of Bucket Overflows n Bucket overflow can occur because of  l Insufficient buckets  l Skew in distribution of records.  This can occur due to two  reasons:  multiple records have same search­key value  chosen hash function produces non­uniform distribution of key  values n Although the probability of bucket overflow can be reduced, it cannot  be eliminated; it is handled by using overflow buckets. ©Silberschatz, Korth and Sudarshan12.52Database System Concepts ­ 5th Edition. Handling of Bucket Overflows (Cont.) n Overflow chaining – the overflow buckets of a given bucket are chained  together in a linked list. n Above scheme is called closed hashing.   l An alternative, called open hashing, which does not use overflow  buckets,  is not suitable for database applications. ©Silberschatz, Korth and Sudarshan12.53Database System Concepts ­ 5th Edition. Hash Indices n Hashing can be used not only for file organization, but also for index­ structure creation.   n A hash index organizes the search keys, with their associated record  pointers, into a hash file structure. n Strictly speaking, hash indices are always secondary indices  l if the file itself is organized using hashing, a separate primary hash  index on it using the same search­key is unnecessary.   l However, we use the term hash index to refer to both secondary  index structures and hash organized files.  ©Silberschatz, Korth and Sudarshan12.54Database System Concepts ­ 5th Edition. Example of Hash Index ©Silberschatz, Korth and Sudarshan12.55Database System Concepts ­ 5th Edition. Deficiencies of Static Hashing n In static hashing, function h maps search­key values to a fixed set of B  of bucket addresses. Databases grow or shrink with time.  l If initial number of buckets is too small, and file grows, performance  will degrade due to too much overflows. l If space is allocated for anticipated growth, a significant amount of  space will be wasted initially (and buckets will be underfull). l If database shrinks, again space will be wasted. n One solution: periodic re­organization of the file with a new hash  function l Expensive, disrupts normal operations n Better solution: allow the number of buckets to be modified dynamically.  ©Silberschatz, Korth and Sudarshan12.56Database System Concepts ­ 5th Edition. Dynamic Hashing n Good for database that grows and shrinks in size n Allows the hash function to be modified dynamically n Extendable hashing – one form of dynamic hashing  l Hash function generates values over a large range — typically b­bit  integers, with b = 32. l At any time use only a prefix of the hash function to index into a  table of bucket addresses.    l Let the length of the prefix be i bits,  0 ≤  i ≤  32.    Bucket address table size = 2i.  Initially i = 0  Value of i grows and shrinks as the size of the database grows  and shrinks. l Multiple entries in the bucket address table may point to a bucket  (why?) l Thus, actual number of buckets is < 2i  The number of buckets also changes dynamically due to  coalescing and splitting of buckets.  ©Silberschatz, Korth and Sudarshan12.57Database System Concepts ­ 5th Edition. General Extendable Hash Structure  In this structure, i2 = i3 = i, whereas i1 = i – 1 (see next  slide for details) ©Silberschatz, Korth and Sudarshan12.58Database System Concepts ­ 5th Edition. Use of Extendable Hash Structure n Each bucket j stores a value ij l All the entries that point to the same bucket have the same values on  the first ij bits.  n To locate the bucket containing search­key Kj: 1. Compute h(Kj) = X 2. Use the first i high order bits of X as a displacement into bucket  address table, and follow the pointer to appropriate bucket n To insert a record with search­key value Kj  l follow same procedure as look­up and locate the bucket, say j.   l If there is room in the bucket j insert record in the bucket.   l Else the bucket must be split and insertion re­attempted (next slide.)  Overflow buckets used instead in some cases (will see shortly) ©Silberschatz, Korth and Sudarshan12.59Database System Concepts ­ 5th Edition. Insertion in Extendable Hash Structure (Cont)  n If i > ij (more than one pointer to bucket j) l allocate a new bucket z, and set ij = iz =  (ij + 1) l Update the second half of the bucket address table entries originally  pointing to j, to point to z l remove each record in bucket j and reinsert (in j or z) l recompute new bucket for Kj and insert record in the bucket (further  splitting is required if the bucket is still full) n If i = ij (only one pointer to bucket j) l If i reaches some limit b, or too many splits have happened in this  insertion, create an overflow bucket  l Else  increment i and double the size of the bucket address table.  replace each entry in the table by two entries that point to the  same bucket.  recompute new bucket address table entry for Kj Now i > ij  so use the first case above.    To split a bucket j when inserting record with search­key value Kj: ©Silberschatz, Korth and Sudarshan12.60Database System Concepts ­ 5th Edition. Deletion in Extendable Hash Structure n To delete a key value,  l locate it in its bucket and remove it.  l The bucket itself can be removed if it becomes empty (with  appropriate updates to the bucket address table).  l Coalescing of buckets can be done (can coalesce only with a  “buddy” bucket having same value of ij and same ij –1 prefix, if it is  present)  l Decreasing bucket address table size is also possible  Note: decreasing bucket address table size is an expensive  operation and should be done only if number of buckets becomes  much smaller than the size of the table  ©Silberschatz, Korth and Sudarshan12.61Database System Concepts ­ 5th Edition. Use of Extendable Hash Structure:   Example  Initial Hash structure, bucket size = 2 ©Silberschatz, Korth and Sudarshan12.62Database System Concepts ­ 5th Edition. Example (Cont.) n Hash structure after  insertion of one Brighton and two Downtown  records ©Silberschatz, Korth and Sudarshan12.63Database System Concepts ­ 5th Edition. Example (Cont.) Hash structure after insertion of Mianus record ©Silberschatz, Korth and Sudarshan12.64Database System Concepts ­ 5th Edition. Example (Cont.) Hash structure after insertion of  three Perryridge records ©Silberschatz, Korth and Sudarshan12.65Database System Concepts ­ 5th Edition. Example (Cont.) n Hash structure after insertion of Redwood and Round Hill records ©Silberschatz, Korth and Sudarshan12.66Database System Concepts ­ 5th Edition. Extendable Hashing vs. Other Schemes n Benefits of extendable hashing:   l Hash performance does not degrade with growth of file l Minimal space overhead n Disadvantages of extendable hashing l Extra level of indirection to find desired record l Bucket address table may itself become very big (larger than  memory)  Cannot allocate very large contiguous areas on disk either  Solution: B+­tree file organization to store bucket address table l Changing size of bucket address table is an expensive operation n Linear hashing is an alternative mechanism  l Allows incremental growth of its directory (equivalent to bucket  address table) l At the cost of more bucket overflows ©Silberschatz, Korth and Sudarshan12.67Database System Concepts ­ 5th Edition. Comparison of Ordered Indexing and Hashing n Cost of periodic re­organization n Relative frequency of insertions and deletions n Is it desirable to optimize average access time at the expense of  worst­case access time? n Expected type of queries: l Hashing is generally better at retrieving records having a specified  value of the key. l If range queries are common, ordered indices are to be preferred n In practice: l PostgreSQL supports hash indices, but discourages use due to  poor performance l Oracle supports static hash organization, but not hash indices l SQLServer supports only B+­trees ©Silberschatz, Korth and Sudarshan12.68Database System Concepts ­ 5th Edition. Bitmap Indices n Bitmap indices are a special type of index designed for efficient  querying on multiple keys n Records in a relation are assumed to be numbered sequentially from,  say, 0 l Given a number n it must be easy to retrieve record n  Particularly easy if records are of fixed size n Applicable on attributes that take on a relatively small number of  distinct values l E.g. gender, country, state,  l E.g. income­level (income broken up into a small number of  levels  such as 0­9999, 10000­19999, 20000­50000, 50000­ infinity) n A bitmap is simply an array of bits ©Silberschatz, Korth and Sudarshan12.69Database System Concepts ­ 5th Edition. Bitmap Indices (Cont.) n In its simplest form a bitmap index on an attribute has a bitmap for  each value of the attribute l Bitmap has as many bits as records l In a bitmap for value v, the bit for a record is 1 if the record has the  value v for the attribute, and is 0 otherwise ©Silberschatz, Korth and Sudarshan12.70Database System Concepts ­ 5th Edition. Bitmap Indices (Cont.) n Bitmap indices are useful for queries on multiple attributes  l not particularly useful for single attribute queries n Queries are answered using bitmap operations l Intersection (and) l Union (or) l Complementation (not)  n Each operation takes two bitmaps of the same size and applies the  operation on corresponding bits to get the result bitmap l E.g.   100110  AND 110011 = 100010                100110  OR  110011 = 110111                        NOT 100110  = 011001 l Males with income level L1:   10010 AND 10100 = 10000  Can then retrieve required tuples.  Counting number of matching tuples is even faster ©Silberschatz, Korth and Sudarshan12.71Database System Concepts ­ 5th Edition. Bitmap Indices (Cont.) n Bitmap indices generally very small compared with relation size l E.g. if record is 100 bytes, space for a single bitmap is 1/800 of space  used by relation.    If number of distinct attribute values is 8, bitmap is only 1% of  relation size n Deletion needs to be handled properly l Existence bitmap to note if there is a valid record at a record location l Needed for complementation  not(A=v):      (NOT bitmap­A­v) AND ExistenceBitmap n Should keep bitmaps for all values, even null value l To correctly handle SQL null semantics for  NOT(A=v):   intersect above result with  (NOT bitmap­A­Null) ©Silberschatz, Korth and Sudarshan12.72Database System Concepts ­ 5th Edition. Efficient Implementation of Bitmap Operations n Bitmaps are packed into words;  a single word and (a basic CPU  instruction) computes and of 32 or 64 bits at once l E.g. 1­million­bit maps can be and­ed with just 31,250 instruction n Counting number of 1s can be done fast by a trick: l Use each byte to index into a precomputed array of 256 elements  each storing the count of 1s in the binary representation  Can use pairs of bytes to speed up further at a higher memory  cost l Add up the retrieved counts n Bitmaps can be used instead of Tuple­ID lists at leaf levels of  B+­trees, for values that have a large number of matching records l Worthwhile if > 1/64 of the records have that value, assuming a  tuple­id is 64 bits l Above technique merges benefits of bitmap and B+­tree indices ©Silberschatz, Korth and Sudarshan12.73Database System Concepts ­ 5th Edition. Index Definition in SQL n Create an index create index  on  () E.g.:  create index  b­index on branch(branch_name) n Use create unique index to indirectly specify and enforce the  condition that the search key is a candidate key is a candidate key. l Not really required if SQL unique integrity constraint is supported n To drop an index  drop index  n Most database systems allow specification of type of index, and  clustering. Database System Concepts, 5th Ed. ©Silberschatz, Korth and Sudarshan See www.db­book.com for conditions on re­use  End of Chapter ©Silberschatz, Korth and Sudarshan12.75Database System Concepts ­ 5th Edition. Partitioned Hashing n Hash values are split into segments that depend on each  attribute of the search­key. (A1, A2, . . . , An) for n attribute search­key n Example:  n = 2, for customer,  search­key being  (customer­street, customer­city) search­key value hash value (Main, Harrison) 101 111 (Main, Brooklyn) 101 001 (Park, Palo Alto) 010 010 (Spring, Brooklyn) 001 001 (Alma, Palo Alto) 110 010 n To answer equality query on single attribute, need to look up  multiple buckets.  Similar in effect to grid files.  ©Silberschatz, Korth and Sudarshan12.76Database System Concepts ­ 5th Edition. Sequential File For account Records ©Silberschatz, Korth and Sudarshan12.77Database System Concepts ­ 5th Edition. Sample account File ©Silberschatz, Korth and Sudarshan12.78Database System Concepts ­ 5th Edition. Figure 12.2 ©Silberschatz, Korth and Sudarshan12.79Database System Concepts ­ 5th Edition. Figure 12.14 ©Silberschatz, Korth and Sudarshan12.80Database System Concepts ­ 5th Edition. Figure 12.25 ©Silberschatz, Korth and Sudarshan12.81Database System Concepts ­ 5th Edition. Grid Files n Structure used to speed the processing of general multiple search­ key queries involving one or more comparison operators. n The grid file has a single grid array and one linear scale for each  search­key attribute.  The grid array has number of dimensions  equal to number of search­key attributes. n Multiple cells of grid array can point to same bucket n To find the bucket for a search­key value, locate the row and column  of its cell using the linear scales and follow pointer ©Silberschatz, Korth and Sudarshan12.82Database System Concepts ­ 5th Edition. Example Grid File for account ©Silberschatz, Korth and Sudarshan12.83Database System Concepts ­ 5th Edition. Queries on a Grid File n A grid file on two attributes A and B can handle queries of all following  forms with reasonable efficiency  l (a1 ≤  A ≤  a2) l (b1 ≤  B ≤  b2) l (a1 ≤  A ≤  a2  ∧  b1 ≤  B ≤  b2),. n E.g., to answer (a1 ≤  A ≤  a2  ∧  b1 ≤  B ≤  b2), use linear scales to find  corresponding candidate grid array cells, and look up all the buckets  pointed to from those cells. ©Silberschatz, Korth and Sudarshan12.84Database System Concepts ­ 5th Edition. Grid Files (Cont.) n During insertion, if a bucket becomes full, new bucket can be created  if more than one cell points to it.  l Idea similar to extendable hashing, but on multiple dimensions l  If only one cell points to it, either an overflow bucket must be  created or the grid size must be increased n Linear scales must be chosen to uniformly distribute records across  cells.  l  Otherwise there will be too many overflow buckets. n Periodic re­organization to increase grid size will help. l But reorganization can be very expensive. n Space overhead of grid array can be high. n R­trees (Chapter 23) are an alternative