Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 8 views

    Hashing in DBMS

    Uploaded by

    srigopi1415
    BCA notes

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Hashing in DBMS

    Uploaded by

    srigopi1415
    8 views4 pages
    BCA notes

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    BCA notes

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    8 views4 pages

    Hashing in DBMS

    Uploaded by

    srigopi1415
    BCA notes

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 4

    Hashing in DBMS

    Hashing technique is very inefficient to search all the index values and reach the
    desired data. Hashing technique is used to calculate the direct location of a data
    record on the disk without using index structure.

    In this technique, data is stored at the data blocks whose address is generated by
    using the hashing function. The memory location where these records are stored is
    known as data bucket or data blocks.

    Static Hashing
    In static hashing, the resultant data bucket address will always be the same. That
    means if we generate an address for EMP_ID =103 using the hash function mod (5)
    then it will always result in same bucket address 3. Here, there will be no change in
    the bucket address.

    Hence in this static hashing, the number of data buckets in memory remains constant
    throughout. In this example, we will have five data buckets in the memory used to
    store the data.

    Operations of Static Hashing


    o Searching a record
    When a record needs to be searched, then the same hash function retrieves the
    address of the bucket where the data is stored.

    o Insert a Record

    When a new record is inserted into the table, then we will generate an address for a
    new record based on the hash key and record is stored in that location.

    o Delete a Record

    To delete a record, we will first fetch the record which is supposed to be deleted.
    Then we will delete the records for that address in memory.

    o Update a Record

    To update a record, we will first search it using a hash function, and then the data
    record is updated.

    Extendible Hashing (Dynamic


    approach to DBMS)
    Extendible Hashing is a dynamic hashing method wherein directories, and
    buckets are used to hash data. It is an aggressively flexible method in which
    the hash function also experiences dynamic changes.
    Main features of Extendible Hashing : The main features in this hashing
    technique are:

     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.
     Buckets: The buckets are used to hash the actual data.
    Basic Structure of Extendible Hashing :

    Frequently used terms in Extendible Hashing :

     Directories: These containers store pointers to buckets. Each directory is


    given a unique id which may change each time when expansion takes
    place. The hash function returns this directory id which is used to navigate
    to the appropriate bucket. Number of Directories = 2^Global Depth.
     Buckets: They store the hashed keys. Directories point to buckets. A
    bucket may contain more than one pointers to it if its local depth is less
    than the global depth.
     Global Depth: It is associated with the Directories. They denote the
    number of bits which are used by the hash function to categorize the
    keys. Global Depth = Number of bits in directory id.
     Local Depth: It is the same as that of Global Depth except for the fact
    that Local Depth is associated with the buckets and not the directories.
    Local depth in accordance with the global depth is used to decide the
    action that to be performed in case an overflow occurs. Local Depth is
    always less than or equal to the Global Depth.
     Bucket Splitting: When the number of elements in a bucket exceeds a
    particular size, then the bucket is split into two parts.
     Directory Expansion: Directory Expansion Takes place when a bucket
    overflows. Directory Expansion is performed when the local depth of the
    overflowing bucket is equal to the global depth.

    You might also like