Microsoft PowerPoint - Lecture9.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - Lecture9.ppt"

暴万
5 years ago
Views:

1 Chap 10. Index 1

2 Indexing Goals: Store large files Support multiple search keys Support efficient insert, delete, and range queries 2

3 Terms(1) Entry sequenced file: Order records by time of insertion. Search with sequential search Index file: Organized, stores pointers to actual records. Could be organized with a tree or other data structure. 3

4 Terms(2) Primary Key: A unique identifier for records. May be inconvenient for search. Secondary Key: An alternate search key, often not unique for each record. Often used for search key. 4

5 Linear Indexing Linear index: Index file organized as a simple sequence of key/record pointer pairs with key values are in sorted order. Linear indexing is good for searching variable-length records. 5

6 Linear Indexing (2) If the index is too large to fit in main memory, a second-level index might be used. 6

7 Tree Indexing (1) Linear index is poor for insertion/deletion. Tree index can efficiently support all desired operations: Insert/delete Multiple search keys (multiple indices) Key range search 7

8 Tree Indexing (2) Difficulties when storing tree index on disk: Tree must be balanced. Each path from root to leaf should cover few disk pages. 8

9 补充 : 二叉平衡树 (AVL 树 ) The AVL tree is named after its two inventors, G.M. Adelson-Velskii and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information." 9

10 一棵 AVL 树或者是空树, 或者是具有下列性质的二叉搜索树 : 它的左子树和右子树都是 AVL 树, 且左子树和右子树的高度之差的绝对值不超过 1 A B D C E A B C D E 不平衡平衡 10

11 结点的平衡因子 (balance factor) 每个结点附加一个数字, 给出该结点右子树的高度减去左子树的高度所得的高度差, 这个数字即为结点的平衡因子 AVL 树任一结点平衡因子只能取 -1, 0, 1 11

12 如果一个结点的平衡因子的绝对值大于 1, 则这棵二叉搜索树就失去了平衡, 不再是 AVL 树如果一棵二叉搜索树是平衡的, 且有 n 个结点, 其高度可保持在 O(log 2 n), 平均搜索长度也可保持在 O(log 2 n) 12

13 是平衡树 1 不是平衡树 13

14 平衡化旋转如果在一棵平衡的二叉搜索树中插入一个新结点, 造成了不平衡此时必须调整树的结构, 使之平衡化平衡化旋转有两类 : 单旋转 ( 左旋和右旋 ) 双旋转 ( 左旋加右旋和右旋加左旋 ) 14

15 每插入一个新结点时,AVL, 树中相关结点的平衡状态会发生改变因此, 在插入一个新结点后, 需要从插入位置沿通向根的路径回溯, 检查各结点的平衡因子如果在某一结点发现高度不平衡, 停止回溯从发生不平衡的结点起, 沿回溯的路径取直接下两层直接下两层的结点 15

16 如果这三个结点处于一条直线上, 则采用单旋转进行平衡化单旋转可按其方向分为左单旋转和右单旋转, 其中一个是另一个的镜像, 其方向与不平衡的形状相关 ; 右单旋转 LL 型左单旋转 RR 型 16

17 如果这三个结点处于一条折线上, 则采用双旋转进行平衡化双旋转分为先左后右和先右后左两类左右双旋转 LR 型右左双旋转 RL 型 17

18 左单旋转 (RotateLeft) 18

19 B +1 h D h A 0 C h E B +2 h D h A +1 C h +1 E B A h 0 C h 0 D h +1 E 在子树 E 中插入新结点, 该子树高度增 1 导致结点 A 的平衡因子变成 +2, 产生不平衡以结点 C 为旋转轴, 反时针旋转 19

20 右单旋转 ( RotateRight) 20

21 D h B A 0-1 h E h C D B -1 A h +1 h -2 E h C D h +1 0 E h B 0 A h C 在子树 D 中插入新结点, 该子树高度增 1 导致结点 A 的平衡因子变成 -2, 产生不平衡以结点 B 为旋转轴, 顺时针旋转 21

22 先左后右双旋转 (RotationLeftRight) 22

23 在 F 或 G 中插入新结点, 该子树高度增 1 导致 A 的平衡因子变成 -2 D h B 插入 A 0 0 F h C E G h h-1 A E F G h h-1 首先以结点 E 为旋转轴, 将结点 B 反时针旋转, 以 E 代替原来 B 的位置, 做左单旋转 D h B h C 左单旋转 23

24 右单旋转 D h B A -2 E 0 F h -2 G h-1 0 h C D h B E A FG C h h-1 h 再以结点 E 为旋转轴, 将结点 A 顺时针旋转, 做右单旋转 24

25 先右后左双旋转 (RotationRightLeft) 25

26 在子树 F 或 G 中插入新结点, 该子树高度增 1 导致 A 的平衡因子变成 2,, 产生不平衡 B 0 h +1 A 0 C 0 D 右单旋转F G h-1 h-1 做右单旋转首先以 D 为旋转轴, 将 C 顺时针旋转, 以 D 代替原 C 的位置, 做右单旋转 0 h E 插入 B 0 h A -1 C D 1 F G h-1 h 0 h E 26

27 B h +2 A 左单 +2 D 旋转 0 0 F C h-1 G E h h A B h D FG h-1 h C E h 再以结点 D 为旋转轴, 将结点 A 反时针旋转, 做左单旋转 27

28 构造二叉平衡 ( 搜索 ) 树的方法在插入过程中, 采用平衡旋转技术依次插入的关键字为 5, 4, 2, 8, 6, 向右旋转一次先向右旋转再向左旋转 28

29 4 向左旋转一次继续插入关键字

30 输入关键码序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 } 插入和调整过程如下左右双旋右单旋

31 左单旋右左双旋

32 左右双旋

33 2-3 Tree (1) A 2-3 Tree has the following properties: 1. A node contains one or two keys 2. Every internal node has either two children (if it contains one key) or three children (if it contains two keys). 3. All leaves are at the same level in the tree, so the tree is always height balanced. The 2-3 Tree has a search tree property analogous to the BST. 33

34 2-3 Tree (2) The advantage of the 2-3 Tree over the BST is that it can be updated at low cost. 34

35 2-3 Tree Insertion (1) 35

36 2-3 Tree Insertion (2) 36

37 2-3 Tree Insertion (3) 37

38 B-Trees (1) The B-Tree is an extension of the 2-3 Tree. The B-Tree is now the standard file organization for applications requiring insertion, deletion, and key range searches. 38

39 B-Trees (2) 1. B-Trees are always balanced. 2. B-Trees keep similar-valued records together on a disk page, which takes advantage of locality of reference. 3. B-Trees guarantee that every node in the tree will be full at least to a certain minimum percentage. This improves space efficiency while reducing the typical number of disk fetches necessary during a search or update operation. 39

40 B-Tree Definition A B-Tree of order m has these properties: The root is either a leaf or has at least two children. Each node, except for the root and the leaves, has between m/2 and m children. All leaves are at the same level in the tree, so the tree is always height balanced. A B-Tree node is usually selected to match the size of a disk block. A B-Tree node could have hundreds of children. 40

41 B-Tree Search (1) Search in a B-Tree is a generalization of search in a 2-3 Tree. 1. Do binary search on keys in current node. If search key is found, then return record. If current node is a leaf node and key is not found, then report an unsuccessful search. 2. Otherwise, follow the proper branch and repeat the process. 41

42 B + -Trees The most commonly implemented form of the B- Tree is the B + -Tree. Internal nodes of the B + -Tree do not store record -- only key values to guild the search. Leaf nodes store records or pointers to records. A leaf node may store more or less records than an internal node stores keys. 42

43 B + -Tree Example 43

44 B + -Tree Insertion 44

45 B + -Tree Deletion (1) 45

46 B + -Tree Deletion (2) 46

47 B + -Tree Deletion (3) 47

48 B-Tree Space Analysis (1) B + -Trees nodes are always at least half full. The B*-Tree splits two pages for three, and combines three pages into two. In this way, nodes are always 2/3 full. Asymptotic cost of search, insertion, and deletion of nodes from B-Trees is (log n). Base of the log is the (average) branching factor of the tree. 48

49 B-Tree Space Analysis (2) Example: Consider a B+-Tree of order 100 with leaf nodes containing 100 records. 1 level B+-tree: 2 level B+-tree: 3 level B+-tree: 4 level B+-tree: Ways to reduce the number of disk fetches: Keep the upper levels in memory. Manage B+-Tree pages with a buffer pool. 49

50 B 树 B 树 B + 树 50

51 B 树是一种平衡的多路搜索树 root

52 在 m 阶的 B- 树上, 每个非终端结点可能含有 : n 个关键字 K i (1 i n) n<m n 个指向记录的指针 D i (1 i n) n+1 个指向子树的指针 A i (0 i n) 多叉树的特性 52

53 非叶结点中的多个关键字均自小至大有序排列, 即 :K 1 < K 2 < < K n A i-1 所指子树上所有关键字均小于 K i A i 所指子树上所有关键字均大于 K i 搜索树的特性 53

54 树中所有叶子结点均不带信息, 且在树中的同一层次上根结点或为叶子结点, 或至少含有两棵子树其余所有非叶结点均至少含有 m/2 棵子树, 至多含有 m 棵子树平衡树的特性 54

55 查找过程从根结点出发, 沿指针搜索结点和在结点内进行顺序 ( 或折半 ) 查找两个过程交叉进行 55

56 若查找成功, 则返回指向被查关键字所在结点的指针和关键字在结点中的位置 ; 若查找不成功, 则返回插入位置 56

57 插入在查找不成功之后, 需进行插入显然, 关键字插入的位置必定在最下层的非叶结点, 有下列几种情况 57

58 插入后, 该结点的关键字个数 n<m, 不修改指针 58

59 插入后, 该结点的关键字个数 n=m, 则需进行结点分裂, 令 s = m/2, 在原结点中保留 (A 0,K 1,, K s-1,a s-1 ); 建新结点 (A s,k s+1,,k n,a n ); 将 (K s,p) 插入双亲结点 59

60 若双亲为空, 则建新的根结点 60

61 下列为 3 阶 B- 树插入关键字 = 60, 90, 30 61

62 删除和插入的考虑相反, 首先必须找到待删关键字所在结点, 并且要求删除之后, 结点中关键字的个数不能小于 m/2-1, 否则, 要从其左 ( 或右 ) 兄弟结点借调关键字, 若其左和右兄弟结点均无关键字可借 ( 结点中只有最少量的关键字 ), 则必须进行结点的合并 62

63 查找性能在含 N 个关键字的 B- 树上进行一次查找, 需访问的结点个数不超过 log m/2 ((N+1)/2)+1 63

64 B + 树是 B- 树的一种变型 64

65 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针 ; 并且, 所有叶子结点彼此相链接构成一个有序链表, 其头指针指向含最小关键字的结点 65

66 每个非叶结点中的关键字 K i 即为其相应指针 A i 所指子树中关键字的最大值所有叶子结点都处在同一层次上, 每个叶子结点中关键字的个数均介于 m/2 和 m 之间 66

67 查找过程在 B + 树上, 既可以进行缩小范围的查找, 也可以进行顺序查找在进行缩小范围的查找时, 不管成功与否, 都必须查到叶子结点才能结束若在结点内查找时, 给定值 K i, 则应继续在 A i 所指子树中进行查找 67

68 插入和删除类似于 B- 树进行, 即必要时, 也需要进行结点的分裂或归并 68

69 root sq

Microsoft PowerPoint - STU_EC_Ch08.ppt

Microsoft PowerPoint - STU_EC_Ch08.ppt 樹德科技大學資訊工程系 Chapter 8: Counters Shi-Huang Chen Fall 2010 1 Outline Asynchronous Counter Operation Synchronous Counter Operation Up/Down Synchronous Counters Design of Synchronous Counters Cascaded Counters