数据结构与算法分析(C语言-英文版)教学课件10-Indexing

1Chapter 10.IndexingWhy indexingLinear IndexingTree indexing2-3 TreesB Trees2Why Indexing Goals:Organize a large collection of records stored on disk.Support efficient insert,delete,and range queriesSupport multiple search keys.3Index FileRecords on diskIndex file on different keysSupport:insert,delete,and range queriesindexindexindexindex4IndexingWhy indexingLinear IndexingTree indexing2-3 TreesB Trees5Linear Indexing(1)Linear index:Index file organized as a simple sequence of(key,record pointer)Key values are sorted.How to search?6Linear Indexing(2)If the index is too large to fit in main memory,a second-level index might be used.7What to improve?Insertion and deletion operation can cause massive update of the index file(Q Q(n)(n)8IndexingWhy indexingLinear IndexingTree indexing2-3 TreesB Trees9Tree IndexingTree index can efficiently support insertion/deletion operationsSearch/insert/delete on BST:(log n)in average case when the tree is balanced.10Tree Indexing(2)BST is not so good:It is expensive to keep BST balanced.Insert 1To keep the BST as a complete binary tree after inserting 1,many records required to refresh.11IndexingWhy indexingLinear IndexingTree indexing2-3 TreesB Trees122-3 Tree(1)The search procedure is similar with BST.Low update cost.132-3 Tree(2)A 2-3 Tree has the following properties:1.A node contains one or two keys2.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.142-3 Tree Searching (log n)Search 2115Insertion-Simple CaseInsert 14Case 1:16Split the node.2320 2124Insert 19232124192020 23212419splitInsertion-SplitCase 2:1723 3020 2124Insert 19311823 30212419203118splitInsertion-Continuous Split23 30212419203118Case 3:1823 3021241920311820212419303118 23split2-3 Tree Insertion(3)1920212419303118 2320212419303118 23 2-3 Tree Insertion(3)20template class TTNode /2-3 tree node structurepublic:Elem lkey;Elem rkey;TTNode*left;TTNode*center;TTNode*right;TTNode()center=left=right=NULL;lkey=rkey=EMPTY;TTNode()bool isLeaf()return left=NULL;lkeyrkeyleftrightcenterImplementation of 2-3 Tree21template bool TTTree:findhelp(TTNode*subroot,const Key&K,Elem&e)const if(subroot=NULL)return false;if(K=getkey(subroot-lkey)e=subroot-lkey;return true;if(subroot-rkey!=EMPTY&K=getkey(subroot-rkey)e=subroot-rkey;return true;if(K lkey)return findhelp(subroot-left,K,e);else if(subroot-rkey=EMPTY)return findhelp(subroot-center,K,e);else if(K rkey)return findhelp(subroot-center,K,e);else return findhelp(subroot-right,K,e);Implementation of 2-3 Tree searchingImplementation of 2-3 Tree searchinglkeyrkeyleftrightcentersubroot22template bool TTTree:inserthelp(TTNode*&subroot,const Elem&e,Elem&retval,TTNode*&retptr)Implementation of 2-3 Tree insertion-Implementation of 2-3 Tree insertion-inserthelpinserthelp22Insert esubrootretptrretvalsubroot23template bool TTTree:inserthelp(TTNode*&subroot,const Elem&e,Elem&retval,TTNode*&retptr)Elem myretv;TTNode*myretp=NULL;if(subroot=NULL)/Empty tree:make new node subroot=new TTNode();subroot-lkey=e;NULLNULLNULLsubroote24template bool TTTree:inserthelp(TTNode*&subroot,const Elem&e,Elem&retval,TTNode*&retptr)Elem myretv;TTNode*myretp=NULL;if(subroot=NULL)/Empty tree:make new node subroot=new TTNode();subroot-lkey=e;else if(subroot-isLeaf()/At leaf node:insert here if(subroot-rkey=EMPTY)/Easy case:not full if(subroot-lkey rkey=e;else subroot-rkey=subroot-lkey;subroot-lkey=e;else splitnode(subroot,e,NULL,retval,retptr);lkey NULLNULLNULLe25template bool TTTree:inserthelp(TTNode*&subroot,const Elem&e,Elem&retval,TTNode*&retptr)Elem myretv;TTNode*myretp=NULL;if(subroot=NULL)/Empty tree:make new node subroot=new TTNode();subroot-lkey=e;else if(subroot-isLeaf()/At leaf node:insert here if(subroot-rkey=EMPTY)/Easy case:not full if(subroot-lkey rkey=e;else subroot-rkey=subroot-lkey;subroot-lkey=e;else splitnode(subroot,e,NULL,retval,retptr);lkeyNULLNULLNULL26template bool TTTree:inserthelp(TTNode*&subroot,const Elem&e,Elem&retval,TTNode*&retptr)Elem myretv;TTNode*myretp=NULL;if(subroot=NULL)/Empty tree:make new node subroot=new TTNode();subroot-lkey=e;else if(subroot-isLeaf()/At leaf node:insert here if(subroot-rkey=EMPTY)/Easy case:not full if(subroot-lkey rkey=e;else subroot-rkey=subroot-lkey;subroot-lkey=e;else splitnode(subroot,e,NULL,retval,retptr);lkeyNULLNULLNULLe27template bool TTTree:inserthelp(TTNode*&subroot,const Elem&e,Elem&retval,TTNode*&retptr)Elem myretv;TTNode*myretp=NULL;if(subroot=NULL)/Empty tree:make new node subroot=new TTNode();subroot-lkey=e;else if(subroot-isLeaf()/At leaf node:insert here if(subroot-rkey=EMPTY)/Easy case:not full if(subroot-lkey rkey=e;else subroot-rkey=subroot-lkey;subroot-lkey=e;else splitnode(subroot,e,NULL,retval,retptr);rkeyNULLNULLNULLlkey28template bool TTTree:inserthelp(TTNode*&subroot,const Elem&e,Elem&retval,TTNode*&retptr)Elem myretv;TTNode*myretp=NULL;else if(e lkey)/Insert in left child inser