DOC PREVIEW
SJSU CS 157A - Data Indexing Presentation

This preview shows page 1-2-3-18-19-36-37-38 out of 38 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 38 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Data IndexingPurposes of Data IndexingConcept of File SystemsDatabase Management SystemsHow DBMS Accesses Data?Time FactorsPhysical Storage DevicesMore Time FactorsPurpose of Data IndexingProperties of Data IndexTwo Types of IndicesOrdered IndexHash IndexDefinition of BucketChoosing Indexing TechniqueIndexing DefinitionsTypes of Ordered IndicesDense IndexDense Index InsertionDense Index DeletionSparse IndexSparse Index InsertionSparse Index DeletionIndex ChoiceChoosing Multi-Level IndexMulti-Level IndexB-Tree IndexThree Types B-Tree NodesFull B-Tree StructureB-Tree InsertionB-Tree Root NodeInsertion into B-TreeB-Tree StructureBranch Node ExampleBranch Nodes Pointing to Leaf NodesB-Tree DeletionInsertion/Deletion ExamplesReferencesData IndexingHerbert A. EvansPurposes of Data Indexing • What is Data Indexing?• Why is it important?Concept of File Systems•Stores and organizes data into computer files.•Makes it easier to find and access data at any given time.Database Management Systems•The file system that manages a database.•Database - is an organized collection of logically related data.How DBMS Accesses Data?•The operations read, modify, update, and delete are used to access data from database.•DBMS must first transfer the data temporarily to a buffer in main memory. •Data is then transferred between disk and main memory into units called blocks.Time Factors•The transferring of data into blocks is a very slow operation. •Accessing data is determined by the physical storage device being used.Physical Storage Devices•Random Access Memory – Fastest to access memory, but most expensive.•Direct Access Memory – In between for accessing memory and cost•Sequential Access Memory – Slowest to access memory, and least expensive.More Time Factors•Querying data out of a database requires more time. •DBMS must search among the blocks of the database file to look for matching tuples.Purpose of Data Indexing•It is a data structure that is added to a file to provide faster access to the data.•It reduces the number of blocks that the DBMS has to check.Properties of Data Index•It contains a search key and a pointer. •Search key - an attribute or set of attributes that is used to look up the records in a file. •Pointer - contains the address of where the data is stored in memory. •It can be compared to the card catalog system used in public libraries of the past.Two Types of Indices•Ordered index (Primary index or clustering index) – which is used to access data sorted by order of values. •Hash index (secondary index or non-clustering index ) - used to access data that is distributed uniformly across a range of buckets.Ordered IndexHash IndexDefinition of Bucket•Bucket - another form of a storage unit that can store one or more records of information.•Buckets are used if the search key value cannot form a candidate key, or if the file is not stored in search key order.Choosing Indexing Technique•Five Factors involved when choosing the indexing technique:•access type•access time•insertion time•deletion time•space overheadIndexing Definitions•Access type is the type of access being used. •Access time - time required to locate the data. •Insertion time - time required to insert the new data. •Deletion time - time required to delete the data. •Space overhead - the additional space occupied by the added data structure.Types of Ordered Indices•Dense index - an index record appears for every search-key value in the file.•Sparse index - an index record that appears for only some of the values in the file.Dense IndexDense Index Insertion•if the search key value does not appear in the index, the new record is inserted to an appropriate position•if the index record stores pointers to all records with the same search-key value, a pointer is added to the new record to the index record •if the index record stores a pointer to only the first record with the same search-key value, the record being inserted is placed right after the other records with the same search-key values.Dense Index Deletion•if the deleted record was the only record with its unique search-key value, then it is simply deleted•if the index record stores pointers to all records with the same search-key value, delete the point to the deleted record from the index record. •If the index record stores a pointer to only the first record with the same search-key value, and if the deleted record was the first record, update the index record to point to the next record.Sparse IndexSparse Index Insertion•first the index is assumed to be storing an entry of each block of the file.•if no new block is created, no change is made to the index.•if a new block is created, the first search-key value in the new block is added to the index.Sparse Index Deletion•if the deleted record was the only record with its search key, the corresponding index record is replaced with an index record for the next search-key value •if the next search-key value already has an index entry, then the index record is deleted instead of being replaced; •if the record being deleted is one of the many records with the same search-key value, and the index record is pointing particularly to it, the index record pointing to the next record with the same search-key value is updated as the reference instead.Index Choice•Dense index requires more space overhead and more memory.•Data can be accessed in a shorter time using Dense Index. •It is preferable to use a dense index when the file is using a secondary index, or when the index file is small compared to the size of the memory.Choosing Multi-Level Index•In some cases an index may be too large for efficient processing. •In that case use multi-level indexing. •In multi-level indexing, the primary index is treated as a sequence file and sparse index is created on it. •The outer index is a sparse index of the primary index whereas the inner index is the primary index.Multi-Level IndexB-Tree Index•B-tree is the most commonly used data structures for indexing. •It is fully dynamic, that is it can grow and shrink.Three Types B-Tree Nodes•Root node - contains node pointers to branch nodes.•Branch node - contains pointers to leaf nodes or other branch nodes.•Leaf node - contains index items and horizontal pointers to other leaf nodes.Full B-Tree StructureB-Tree Insertion•First the DBMS looks up the


View Full Document

SJSU CS 157A - Data Indexing Presentation

Documents in this Course
SQL

SQL

18 pages

Lecture

Lecture

44 pages

Chapter 1

Chapter 1

56 pages

E-R Model

E-R Model

16 pages

Lecture

Lecture

48 pages

SQL

SQL

15 pages

SQL

SQL

26 pages

Lossless

Lossless

26 pages

SQL

SQL

16 pages

Final 3

Final 3

90 pages

Lecture 3

Lecture 3

22 pages

SQL

SQL

25 pages

Load more
Download Data Indexing Presentation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Data Indexing Presentation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Data Indexing Presentation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?