PowerPoint 演示文稿

EXTENDIBLE HASHING.

W h a t i s e x t e n d a b le h a s h i n g ?. Extendible Hashing is a dynamic hashing method wherein directories, and buckets are used to hash data..

MAIN FEATURES OF EXTENDIBLE HASHING:. Directories: The directories store addresses of the buckets in pointers. An id is assigned to each directory which may change each time when Directory Expansion takes place..

B a s i c W o r k i n g. Analyse d a t a e l e m e nts C o n v e rt i n t o b i n a r y f o r m at C h e c k g l o b a l d e p t h o f d i r e c t o r y I d e n t ify t h e d i r e c t o ry N a v i g a t ion I n s e r t i o n a n d o v e r f l ow c h e c k T a c k l i n g o v e r f l o w c o n d i t ion d u r i ng d a t a i n s e r t i on R e h a s h i n g o f s p l i t b u c k e t e l e m e nts.

Algorithm: Step 1 – Analyze Data Elements: Data elements may exist in various forms eg. Integer, String, Float, etc.. Step 2 – Convert into binary format: Convert the data element in Binary form. For string elements, consider the ASCII equivalent integer of the starting character and then convert the integer into binary form. Step 3 – Check Global Depth of the directory..

Step 4 – Identify the Directory: Consider the ‘Global-Depth’ number of LSBs in the binary number and match it to the directory id..

Step 7 – Tackling Over Flow Condition during Data Insertion: Many times, while inserting data in the buckets, it might happen that the Bucket overflows. In such cases, we need to follow an appropriate procedure to avoid mishandling of data. First, Check if the local depth is less than or equal to the global depth. Then choose one of the cases below. Case1: If the local depth of the overflowing Bucket is equal to the global depth, then Directory Expansion, as well as Bucket Split, needs to be performed. Then increment the global depth and the local depth value by 1. And, assign appropriate pointers. Directory expansion will double the number of directories present in the hash structure. Case2: In case the local depth is less than the global depth, then only Bucket Split takes place. Then increment only the local depth value by 1. And, assign appropriate pointers..

Step 8 – Rehashing of Split Bucket Elements: The Elements present in the overflowing bucket that is split are rehashed w.r.t the new global depth of the directory. Step 9 – The element is successfully hashed..

Why do we use Extendible hashing?. Extendible hashing is a dynamically updateable disk-based index structure which implements a hashing scheme utilizing a directory. The index is used to support exact match queries, i.e., find the record with a given key. Compared with the B+-tree index which also supports exact match queries (in logarithmic number of I/Os), Extendible Hashing has better expected query cost O(1) I/O. Compared with linear hashing, extendible hashing does not have any overflow page. Overflows are handled by doubling the directory which logically doubles the number of buckets. Physically, only the overflown bucket is split..

T h a n k You.

By: Abhishek Biswas RA2011003010029 Aryansh Mohata RA2011003010017 Kashif Khan RA2011003010038 Anant Dev Kapoor RA2011003010060 Aishik Roy RA2011003010039.