Notes on DBMS File structure and Index

1. In DBMS, data and information is stored in file formats on physical storage level.
2. A file is a sequence of records stored in binary format. 
3. Records are table rows of relational databases. Collection of records are contained in pages which are the internal basic structure to organize the data in the database files. (Page is the smallest unit of data for memory management in a virtual memory operating system.)
4. A single file may contain several pages. 
5. Each record has a unique identifier called a record id, or rid for short. 

Heap files

The simplest file structure is an unordered file or heap file. The data in the pages of a heap file is not ordered in any way, and the only guarantee is that one can retrieve all records in the file by repeated requests for the next record. Every record in the file has a unique rid (record id), and every page in a file is of the same size.

Supported operations on a heap file include create and destroy files, insert a record, delete a record with a given rid, get a record with a given rid, and scan all records in the file. To get or delete a record with a given rid, note that we must be able to find the id of the page containing the record, given the id of the record. In modern Dbms, record ids are implemented as page id and slot number.

We must keep track of the pages in each heap file in order to support scans, and we must keep track of pages that contain free space in order to implement insertion efficiently.

Intro to Indexes

Sometimes we want to find all records that have a given value in a particular field. If we can find the rids of all such records, we can locate the page containing each record from the record's rid; however, the heap file organization does not help us to find the rids of such records. So here comes an index which is an auxiliary data structure to help us find rids of records that meet a selection condition.

This notion is just similar to library catalog which helps reader search a book by many criteria such as author, name, and published date.

In another word, index is a file containing search key, which is a collection of one or more fields on which we are building index; values of those fields are organized according to particular search efficient data structures (B+ tree) that also includes a low-level disk block address (data entries) or direct link to the complete row of data in data files.



In most cases, an index is used to quickly locate the data record(s) from which the required data is read. In other words, the index is only used to locate data records in the table and not to return data.
But in some cases, index that is used could contain required data fields and return data. (2) Example of indexing could be like that if we wanted to build an index to improve the efficiency of queries about employees of a given age, we could build an index on the age attribute of the employee dataset. The records stored in an index file, which we refer to as entries allow us to find data records with a given search key value.

One could build multiple indexes on a single dataset. For example; if we wanted to build indexes on both of age and salary fields of employee dataset, at most one of the indexes can contain data entries which are actual data records, and another one is separate index file with left field as search key. 

Properties of indexes

Non clustered

The data is present in arbitrary order, but the logical ordering is specified by the index. The data rows may be spread throughout the table regardless of the value of the indexed column or expression. The non-clustered index tree contains the index keys in sorted order, with the leaf level of the index containing the pointer to the record (page and the row number in the data page in page-organized engines; row offset in file-organized engines).

In a non-clustered index,
The physical order of the rows is not the same as the index order.
The indexed columns are typically non-primary key columns used in JOIN, WHERE, and ORDER BY clauses.

There can be more than one non-clustered index on a database table.

Clustered 

Clustering alters the data block into a certain distinct order to match the index, resulting in the row data being stored in order. Therefore, only one clustered index can be created on a given database table. Clustered indices can greatly increase overall speed of retrieval, but usually only where the data is accessed sequentially in the same or reverse order of the clustered index, or when a range of items is selected.

Since the physical records are in this sort order on disk, the next row item in the sequence is immediately before or after the last one, and so fewer data block reads are required. The primary feature of a clustered index is therefore the ordering of the physical data rows in accordance with the index blocks that point to them. Some databases separate the data and index blocks into separate files, others put two completely different data blocks within the same physical file(s).

Types of indexes

Dense versus Sparse Indexes

An index is said to be dense if it contains (at least) one data entry for every search key value that appears in a record in the indexed file. A sparse index contains one entry for each page of records in the data file. 

Primary and Secondary Indexes

An index on a set of fields that includes the primary key is called a primary index. An index that is not a primary index is called a secondary index. Two data entries are said to be duplicates if they have the same value for the search key field associated with the index. A primary index is guaranteed not to contain duplicates, but an index on other fields can contain duplicates. Thus, in general, a secondary index contains duplicates. 

Used references:

(1) https://en.wikipedia.org/wiki/Database_index

(2) Raghu Ramakrish - "Database Management Systems" 2nd