kc第12讲-数据索引技术.ppt

Basic Concepts Example of B+-Tree -样式 Non-Leaf Nodes in B+-Trees(非叶节点) Non leaf nodes form a multi-level sparse index on the leaf nodes. For a non-leaf node with m pointers: m?n All the search-keys in the subtree to which P1 points are less than K1 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 All the search-keys in the subtree to which Pn points have values greater than or equal to Kn–1 *Queries on B+-Trees(查询)注:参5版教材-大同小异 Find all records with a search-key value of k. N=root Repeat Examine N for the smallest search-key value k. If such a value exists, assume it is Ki. Then set N = Pi Otherwise k ? Kn–1. Set N = Pn Until N is a leaf node If for some i, key Ki = k follow pointer Pi to the desired record or bucket. Else no record with search-key value k exists. Queries on B+-Trees (节点大小效率) If there are K search-key values in the file, the height of the tree is no more than ?log?n/2?(K)?. K-记录数 A node is generally the same size as a disk block, typically 4 kilobytes (4k) and n is typically around 100 (40 bytes per index entry). n-节点大小 With 1 million search key values and n = 100 at most log50(1,000,000) = 4 nodes are accessed in a lookup. Contrast this with a balanced binary tree with 1 million search key values — around 20 nodes are accessed in a lookup above difference is significant since every node access may need a disk I/O, costing around 20 milliseconds 毫秒 Updates on B+-Trees:Insertion(插入更新算法) Find the leaf node in which the search-key value would appear 索引项已存在时: If the search-key value is already present in the leaf node Add record to the main file修改主文件 If necessary add a pointer to the bucket.必要时(当索引项不是主码时，这时叶节点不是直接指向文件记录，而是间接指向指针桶，如象p.323图12.9)修改相应指针桶 索引项不存在时：If the search-key value is not present, then add the record to the main file (and create a bucket if necessary) 节点未满时：