3.0 INTRODUCTION

Just as arrays, lists, trees and other data structures are used to implement data organization in main memory, a number of strategies are used to support the organization of data in secondary memory.

Figure 1 : File organization techniques

In this unit we will look at different strategies of organizing data in the secondary memory. In this unit, we are concerned with obtaining data representation for files on external storage devices so that required functions (e.g. retrieval, update) may be carried out efficiently. The particular organization most suitable for any application will depend upon such factors as the kind of external storage available, types of queries allowed, number of keys, mode of retrieval and mode of update. The figure 1 illustrates different file organizations based on an access key.

After going through this unit you will be able to:

1. Sequential
2. Relative
3. Indexed sequential
4. Multi-key

There are two basic ways that the file organization techniques differ. First the organization determines the file's record sequencing, which is the physical ordering of the records in storage.

Second, the file organization determines the set of operation necessary to find particular records. Having particular values in search-key fields typically identifies individual records. This data field may or may not have duplicate values in file; the field can be a group or elementary item. Some file organization techniques provide rapid accessibility on a variety of search key; other techniques support direct access only on the value of a single one.

The most basic way to organize the collection of records that from a file is to use sequential organization. In a sequentially organized file records are written consecutively when the file is created and must be accessed consecutively when the file is later used for input (figure 2).

Figure 2 : Structure of sequential file

In a sequential file, records are maintained in the logical sequence of their primary key values. The processing of a sequential file is conceptually simple but inefficient for random access. However, if access to the file is strictly sequential, a sequential file is suitable. A sequential file could be stored on a sequential storage device such as a magnetic tape.

Search for a given record in a sequential file requires, on average, access to half the records in the file. Consider a system where the file is stored on a direct access device such as a disk. Suppose the key value is separated from the rest of the record and a pointer is used to indicate the location of the record. In such a system, the device may scan over the key values at rotation speeds and only read in the desired record. A binary or logarithmic search technique may also be used to search for a record. In this method, the cylinder on which the required record is stored is located by a series of decreasing head movements. The search having been localized to a cylinder may require the reading of half the tracks, on average, in the case where keys are embedded in the physical records, or require only a scan over the tracks in the case where keys are also stored separately.

Updating usually requires the creation of a new file. To maintain file sequence, records are copied to the point where amendment is required. The changes are then made and copied into the new file. Following this, the remaining records in the original file are copied to the new file. This method of updating a sequential file creates an automatic backup copy. It permits updates of the type U1 through U4.

Addition can be handled in a manner similar to updating. Adding a record necessitates the shifting of all records from the appropriate point to the end of file to create space for the new record. Inversely, deletion of a record requires a compression of the file space, achieved by the shifting of records. Changes to an existing record may also require shifting if the record size expands or shrinks.

The basic advantage offered by a sequential file is the ease of access to the next record, the simplicity of organization and the absence of auxiliary data structures. However, replies to simple queries are time consuming for large files. Updates, as seen above, usually require the creation of a new file. A single update is an expensive proposition if a new file must be created. To reduce the cost per update, all such requests are hatched, sorted in the order of the sequen1tial file, and then used to update the sequential file in a single pass. Such a file, containing the updates to be made to a sequential file, is sometimes referred to a transaction file.

In the batched mode of updating, a transaction file of update records is made and then sorted in the sequence of the sequential file. Ale update process requires the examination of each individual record in the original sequential file (the old master rile). Records requiring no changes are copied directly to a new file (the new master rile); records requiring one or Wore changes are written into the new master file only after all necessary changes have been made. Insertions of new records are made in the proper sequence. They are written into the new master file at the appropriate place. Records to be deleted are not copied to the new master file. A big advantage of this method of update is the creation of an automatic backup copy. The new master file can always be recreated by processing the old master file and the transaction file.

Figure 3 : A file with empty spaces for record insertions

A possible method of reducing the creation of a new file at each update run is to create the original file with "holes" (space left for the addition of new records, as shown in the last figure). As such, if a block could hold K records, then at initial creation it is made to contain only L * K records, where 0 < L < 1 is known as the loading factor. Additional space may also be earmarked for records that may "overflow" their blocks, e.g., if the record ri logically belongs to block Bi but the physical block Bi does not contain the requisite free space. This additional free space is known as the overflow area. A similar technique is employed in index-sequential files.

The retrieval of a record from a sequential file, on average, requires access to half the records in the file, making such inquiries not only inefficient but very time consuming for large files. To improve the query response time of a sequential file, a type of indexing technique can be added.

An index is a set of y, address pairs. Indexing associates a set of objects to a set of orderable quantities, which are usually smaller in number or their properties provide a mechanism for faster search. The purpose of indexing is to expedite the search process. Indexes created from a sequential (or sorted) set of primary keys are referred to as index sequential. Although the indices and the data blocks are held together physically, we distinguish between them logically. We shall use the term index file to describe the indexes and data file to refer to the data records. The index is usually small enough to be read into the processor memory.

3.4.1 Types of Indexes

The idea behind an index access structure is similar to that behind the indexes used commonly in textbooks. A textbook index lists important terms at the end of the book in alphabetic order. Along with each term, a list of page numbers where the term appears is given. We can search the index to find a list of addresses - page numbers in this case - and use these addresses to locate the term in the textbook by searching the specified pages. The alternative, if no other guidance is given, is to sift slowly through the whole textbooks word by word to find the term we are interested in, which corresponds to doing a linear search on a file. Of course, most books do have additional information, such as chapter and section titles, which can help us find a term without having to search through the whole book. However, the index is the only exact indication of where each term occurs in the book.

An index is usually defined on a single field of a file, called an indexing Field. The index typically stores each value of the index field along with a list of pointers to all disk blocks that contain a record with that field value. The values in the index are ordered so that we can do a binary search on the index. The index file is much smaller than the data file, so searching the index using binary search is reasonably efficient. Multilevel indexing does away with the need for binary search at the expense of creating indexes to the index itself!

There are several types of indexes. A primary index is an index specified on the ordering key field of an ordered file of records. Recall that an ordering key field is used to physically order the file records on disk, and every record has a unique value for that field. If the ordering field is not a key field that is, several records in the file can have the same value for the ordering field another type of index, called a clustering index, can be used. Notice that a file can have at most one physical ordering field, so it can have at most one primary index or one clustering index, but not both. A third type of index, called a secondary index, can be specified on any non-ordering field of a file. A file can have several secondary indexes in addition to its primary access method. In the next three subsections we discuss these three types of indexes.

Primary Indexes

A primary index is an ordered file whose records are of fixed length with two fields. The first field is of the same data types as the ordering key field of the data file, and the second field is a pointer to a disk block - a block address. The ordering key field is called the primary key of the data file there is one index entry (or index record) in the index file for each block in the data file. Each index entry has the value of the primary key field for the first record in a block and a pointer to other block as its two field values. We will refer to the two field values of index entry i as K (i), P (i).

To create a primary index on the ordered file shown in figure 4, we use the Name field as the primary key, because that is the ordering key field of the file (assuming that each value of NAME is unique).

Figure 4 : Some blocks on an ordered (sequential) file of EMPLOYEE records with NAME as the ordering field

Each entry in the index will have a NAME value and a pointer. The first three index entries would be:

< K(1) = (Aaron, Ed), P(I)= address of block 1 >

< K(2) = (Adams, John), P(I) = address of block 2 >

< K(3) = (Alexander, Fd), P(3) = address of block 3 >

Figure 5 : Illustrating internal hashing data Structures. (a) Array of M Positions for use in hashing. (b) Collision resolution by chaining of records.

Figure 6 illustrates this Primary index. The total number of entries in the index will be the same as the number of disk block in the ordered data file.The first record in each block of the data file. The first record in each block of the data file is called the anchor record of the block, or simple the block anchor (a scheme called the anchor record of similar to the one described here can be used, with the last record in each block, rather than the first as the block anchor. A primary index is an example of what is called a non-dense index because it includes an entry for each disk block of the data file rather than for every record in the data file. A dense index, on the other hand, contains an entry for every record in the file.

The index file for a primary index needs substantially fewer blocks than the data file for two reasons. First, there are fewer index entries than there are records in the data file because an entry exists for each whole block of the data file rather than for each record. Second, each index entry is typically smaller in size than a data record because it has only two fields, so more index entries than data records will fit in one block. A binary search on the index file will hence require fewer block accesses than a binary search on the data file.

Figure 6 : Primary index on the ordering key field of the file shown in figure 5

A record whose primary key value is K will be in the block whose address is P(i), where Ki < K< (i + 1). The ith block in the data file contains all such records because of the physical ordering of the file records on the primary key field, we do a binary search on the index file to find the appropriate index entry i, then retrieve the data file block whose address is P(i). Notice that the above formula would not be correct if the data file was ordered on a non-key field that allows multiple records to have the same ordering field value. In that case the same index value as that in the block anchor could be repeated in the last records of the previous block. Example 1 illustrates the saving in block accesses when using an index to search for a record.

Example 1 : Suppose we have an ordered file with r = 30,000 records stored on a disk with block size B = 1024 bytes. File records are of fixed size and unplanned with record length R 100 bytes. The blocking factor for the file would be bfr L[(B/R)] = [(1024/100)]=10 records per block. The number of blocks needed for the file is b = [(r/bfr)] = [(30,000/10)]= 3000 blocks. A binary search on the data file would need approximately [(log2b)]= [(log23000)]= 12 block accesses.

Now suppose the ordering key field of the file is V = 9 bytes long, a block pointer is P = 6 bytes long, and we construct a primary index for the file. The size of each index entry is Ri=(9 + 6) = 15 bytes, so the blocking factor for the index is bfri= [(B/R)]= [(1024/15)] = 68 entries per block.

The total number of index entries ri is equal to the number of blocks in the data file, which is 3000. The number of blocks needed for the index is hence bi = [ri/bfri)]= [(3OOO/68)]= 45 blocks. To perform a binary search on the index file would need [ (log2bi)] = [(log245)]=6 block accesses. To search for a record using the index, we need one additional block access to the data file for a total of 6 + 1 = 7 block accesses - an improvement over binary search on the data file, which required 12 block accesses.

A major problem with a primary index - as with any ordered file - is insertion and deletion of records. With a primary index, the problem is compounded because if we attempt to insert a record in its correct position in the data file, we not only have to move records to make space for the new record but also have to change some index entries because moving records will change the anchor records of some blocks. We can use an unordered overflow file. Another possibility is to use a linked list of overflow records for each block in the data file. We can keep the records within each block and its overflow-linked list sorted to improve retrieval time. Record deletion can be handled using deletion markers.

Clustering Indexes

If records of a file are physically ordered on a non-key field that does not have a distinct value, for each record, that field is called the clustering field of the file. We can create a different type of index, called a clustering index, to speed up retrieval of records that have the same value for the clustering field.

Figure 7 : A clustering Index on the DEPTNUMBER ordering field of an EMPLOYEE file

This differs from a primary index, which requires that the ordering field of the data file have a distinct value for each record.

A clustering index is also an ordered file with two fields; the first field is of the same type as the clustering field of the data file and the second field is a block pointer. There is one entry in the clustering index for each distinct value of the clustering field, containing that value and a pointer to the first block in the data file that has a record with that value for its clustering field.

Figure 8 : Clustering index with separate blocks for each group of records with the same value for the clustering field

Figure 7 shows an exam le of a data file with a clustering index. Note the record and record deletion still cause considerable problems because the data records are physically ordered. To alleviate the problem of insertion, it is common to reserve a whole block for each value of the clustering field; all records with that value are placed in the block. If more than one block is needed to store the records for a particular value, additional blocks are allocated and linked together. This makes insertion and deletion relatively straightforward. Figure 8 shows this scheme.

A clustering index is another example of a non-dense index because it has an entry for every distinct value of the indexing field rather than for every record in the file.

Secondary Indexes

A secondary index also is an ordered file with two fields, and, as in the other indexes, the second field is a pointer to a disk block. The first field is of the same data type as some non-ordering field of the data file. The field on which the secondary index is constructed is called an indexing field of the file, whether its values are distinct for every record or not. There can be many secondary indexes, and hence indexing fields, for the same file.

We first consider a secondary index on a key field - a field having a distinct value for every record in the data file. Such a field is sometimes called a secondary key for the file. In this case there is one index entry for each record in the data file, which has the value of the secondary key for the record and a pointer to the block in which the record is stored. A secondary index on a key field is a dense index because it contains one entry for each record in the data file.

We again refer to the two field values of index entry i as K(i), P(i). The entries are ordered by value of K(i), so we can use binary search on the index. Because the records of the data file are not physically ordered by values of the secondary key field, we cannot use block

Figure 9 : A dense secondary Index on a non ordering key field of a file

anchors. That is why an index entry is created for each record in the data file rather than for each block as in the case of a primary index. Figure 9 illustrates a secondary index on a key attribute of a data file. Notice that in figure 9 the pointers P(i) in the index entries are block pointers, not record pointers. Once the appropriate block is transferred to main memory, a search for the desired record within the block can be carried out.

A secondary index will usually need substantially more storage space than a primary index because of its larger number of entries. However, the improvement in search time for an arbitrary record is much greater for a secondary index than it is for a primary index, because we would have to do a linear search on the data file if the secondary index did not exist. For a primary index, we could still use binary search on the main file even if the index did not exist because the primary key field physically orders the records. Example 2 illustrates the improvement in number of blocks accessed when using a secondary index to search for a record.

Example 2: Consider the file of Example 1 with r = 30,000 fixed- length records of size R 100 bytes stored on a disk with block size B = 1024 bytes. The file has b = 3000 blocks as calculated in Example 1. To do a linear search on the file, we would require b/2=3000/2=1500 block accesses on the average.

Suppose we construct a secondary index on a non-ordering key field of the file that is V=9 bytes long. As in Example 1, a block pointer is P=6 bytes long, so each index entry is R. (9+6)=15 bytes, and the blocking factor for the index is bfri = [(B/Ri)]=[(1024/15)]=68 entries per block. In a dense secondary index such as this, the total number of index entries is ri is equal to the number of records in the data file, which is 30,000. The number of blocks needed for the index is hence bi=(ri/bfri)=(30,000/68) = 442 blocks.

Compare this to the 45 blocks needed by the non-dense primary index in Example 1.

A binary search on this secondary index needs (log2bi)=(log2442)= 9 block accesses. To search for a record using the index, we need an additional block access to the data file for a total of 9 + 1 = 10 block accesses - a vast improvement over the 1500 block accesses needed on the average for a linear search.

Figure 10 :A secondary index on a non key field implemented using one level of indirection so that index entries are fixed length and have unique field values

We can also create a secondary index on a non-key field of a file. In this case numerous records in the data file can have the same value for the indexing field. There are several options for implementing such an index:

Notice that a secondary index provides a logical ordering on the records by the indexing field. If we access the records in order of the entries in the secondary index, we get them in order of the indexing field.

Multilevel Indexing Schemes: Basic Technique

In a full indexing scheme, the address of every record is maintained in the index. For a small file, this index would be small and can be processed very efficiently in main memory.

Figure 11 : Hierarchy of Indexes

For a large file, the index's size would pose problems. It is possible to create a hierarchy of indexes with the lowest level index pointing to the records, while the higher-level indexes point to the indexes below them (figure 11). The higher-level indices are small and can be moved to main memory, allowing the search to be localized to one of the larger lower level indices.

The lowest level index consists of the pair for each record in the file; this is costly in terms of space. Updates of records require changes to the index file as well as the data file. Insertion of a record requires that its pair be inserted in the index at the correct point, while deletion of a record requires that the pair be removed from the index. Therefore, maintenance of the index is also expensive. In the simplest case, updates of variable length records require that changes be made to the address field of the record entry. In a variation of this scheme, the address value in the lowest level index entry points to a block of records and the key value represents the highest key value of records in this block. Another variation of this scheme is described in the next section.

3.4.2 Structure of Index Sequential Files

An index-sequential file consists of the data plus one or more levels of indexes. When inserting a record, we have to maintain the sequence of records and this may necessitate shifting subsequent records. For a large file this is a costly and inefficient process. Instead, the records that overflow their logical area are shifted into a designated overflow area and a pointer is provided in the logical area or associated index entry points to the overflow location. This is illustrated below (figure 12). Record 165 is inserted in the original logical block causing a record to be moved to an overflow block.

Figure 12 : Overflow of record

Multiple records belonging to the same logical area may be chained to maintained logical sequencing. When records are forced into the overflow areas as a result of insertion, the insertion process is simplified, but the search time is increased. Deletion of records from index-sequential flies creates logical gaps; the records are not physically removed but only flagged as having been deleted. If there were a number of deletions, we may have a great amount of unused space.

An index-sequential file is therefore made up of the following components:

The primary data area contains the records written by the users' programs. The records are written in data blocks in ascending key sequence. These data blocks are in turn stored in ascending sequence in the primary data area. The highest key of the logical records contained in them sequences the data blocks.

ALGORITHM: OVERFLOW ADDITIONS

1. Find the first available position in the overflow area.

2. Move the record to this position

3. If this record is the record of lowest key in the overflow area, place the pointer to this record in the overflow entry of the track index and move the old value in the track index to the pointer field of the newly added record. If this is not the case, move the address of the new record to the pointer field of the record in the overflow area that precedes it in sorted sequence and place the old value of the pointer into the pointer field of the new record.

Creating an ISAM File

An ISAM file must be loaded sequentially in sorted order by record key. ISAM win defect a record out of order. Any dummy records to be added to the file should be placed in the input data stream in sequence. These records are best added where record additions are expected to take place. For instance, a credit card company may expect in the near future to add records whose keys range between 416-250-000 and 416-275-000 as a new district of credit card holders is opened up. In this case, dummy records with these keys can be created and added to the file during file creation. Another possibility is simply to scatter a certain percentage of dummy records throughout the file. This is not nearly as effective as always possible (there may be no unused keys in the file). Recall that a dummy record is only ignored if it is at the end of a track. It will stay on a track until it is replaced by a valid record with the same key or pushed off the end by a new insertion.

Once the file is in use, any record whose deletion is desired can be turned into a dummy record by writing HIGH-VALUES in its first character position. This is a useful feature, especially in a credit card situation or phone number list where inactive customers can be replaced.

So what is the significance of the ISAM organization?

Advantages of ISAM indexes:

1. Because the whole structure is ordered to a large extent, partial (LIKE y%) and range (BETWEEN 12 and 18) based retrievals can often benefit from the use of this type of index.
2. ISAM is good for static tables because there are usually fewer index levels than B-tree.
3. Because the Index is never updated, there are never any locking contention problems within the index itself --- this can occur in B-tree indexes, especially when they get to the point of 'splitting' to create another level.
4. In general there are fewer disk I/Os required to access data, provided there is no overflow.
5. Again if little overflow is evident, then data tends to be clustered. This means that single block retrieval often brings back rows with similar key values and of relevance to the initiating query.

Disadvantages of ISAM indexes:

1. ISAM is still not as quick as some (hash organization, dealt with later, is quicker).
2. Overflow can be a real problem in highly volatile tables.
3. The sparse index means that the lowest level of index has only the highest key for a specific data page, and therefore the block (or more usually a block header), must be searched to locate specific rows in a block.

In a nutshell therefore, these are the two types of indexing generally available. As I have already said, indexes can be either created on one single, or several groups, of columns within single tables, and generally the ability to create them should be a privilege under the control of the DBA. Indexes usually take up significant disk space, and although generally of significant benefit in the case of data retrieval, they can slow down insert/update and delete operation because of overhead in maintaining the index, and in ISAM of ensuring the logical organization of the data rows.

The presence of an index does not mean that the RDBMS will always use it, a reality of life discussed later; and it is also true that it is not generally possible to pick and choose which index will be used under which conditions. If follows, therefore, that the administration of indexes should be done centrally, with great case, and should be a major consideration in the physical design stage of a project due to its application dependence.

Before leaving these types of access mechanisms and moving on to an explanation of hashing, it is worth listing some of the other functions that may be required within the context of manipulating indexes.

3.4.3 VSAM

The major disadvantage of the index-sequential organization is that as the file grows, performance deteriorates rapidly because of overflows, and consequently there arises the need for periodic reorganization. Reorganization is an expensive process and the file becomes unavailable during reorganization. The virtual storage access method (VSAM) is IBM’s advanced version of the index-sequential organization that avoids these disadvantages. The system is immune to the characteristics of the storage medium, which could be considered as a pool of blocks.

The VSAM files are made up of two components: the index and data. However, unlike index-sequential organization, overflows are handled in a different manner. The VSAM index and data are assigned to distinct blocks of virtual storage called a control interval. To allow for growth, each time a data block overflows it is divided into two blocks and appropriate changes are made to the indexes to reflect this division.

Indexing are maintained through B-Tree, for detail consult the reference book

B-TREES

The basic B-tree structure was discovered by R.Bayer and E. McCreight (1970) of Boeing Scientific Research Labs and has grown to become one of the most popular techniques for organizing an index structure. Many variations on the basic B-tree have been developed; we cover the basic structure first and then introduce some of the variations.

The B-tree is known as the balanced sort tree, which is useful for external sorting. There are strong uses of B-trees in a database system as pointed out by D.Comer (1979): "While no single scheme can be optimum for all applications, the technique of organizing a file and its index called the B -tree is, The facto, the standard organization for indexes in a database system."

The file is a collection of records. The index refers to a unique key, associated with each record. One application of B- trees is found in IBM's Virtual Storage Access Method (VSAM) file organization. Many data manipulation tasks require data storage only in main memory. For applications with a large database running on a system with limited company, the data must be stored as records on secondary memory (disks) and be accessed in pieces. The size of a record can be quite large, as shown below:

struct DATA
{
int ssn;
char name [80];
char address [80];
char schoold [76];
struct DATA * left; /* main memory addresses */
struct DATA * right; /* main memory addresses */
d_block d_left; /* disk block address */
d_block d_right; /* disk block address */
}

Advantages of Btree indexes:

1. Because there is no overflow problem inherent with this type of organization it is good for dynamic table - those that suffer a great deal of insert / update / delete activity.
2. Because it is to a large extent self-maintaining, it is good in supporting 24-hour operation.
3. As data is retrieved via the index it is always presented in order.
4. 'Get next' queries are efficient because of the inherent ordering of rows with in the index blocks.
5. Btree indexes are good for very large tables because they will need minimal reorganization.
6. There is predictable access time for any retrieval (of the same number of rows of course) because the Btree structure keeps itself balanced, so that there is always the same number of index levels for every retrieval. Bear in mind of course, that the number of index levels does increase both with the number of records and the length of the key value.

Because the rows are in order, this type of index can service range type enquiries, of the type below, efficiently.

SELECT ... WHERE COL BETWEEN X AND Y.

Disadvantages of Btree indexes:

1. For static tables, there are better organizations that require fewer I/0s. ISAM indexes are preferable to Btree in this type of environment.
2. Btree is not really appropriate for very small tables because index look-up becomes a significant part of the overall access time.
3. The index can use considerable disk space, especially in products, which allow different users to create separate indexes on the same table/column combinations.
4. Because the indexes themselves are subject to modification when rows are updated, deleted or inserted, they are also subject to locking which can inhibit concurrency.

So to conclude this section on Btree indexes, it is worth stressing that this structure is by far and away the most popular, and perhaps versatile, of index structures supported in the world of the RDBMS today. Whilst not fully optimized for certain activity, it is seen as the best single compromise in satisfying all the different access methods likely to be required in normal day-to-day operation.

In the index-sequential file organization considered in the previous sections, the mapping from the search-key value to the storage location is via index entries. In direct file

Figure 20 : Mapping from a key value to an address value

organization, the key value is mapped directly to the storage location. The usual method of direct mapping is by performing some arithmetic manipulation of the key value. This process is called hashing. Let us consider a hash function h that maps the key value k to the value h(k). The value h(k) is used as an address and for our application we require that this value be in some range. If our address area for the records lies between S1 and S2, the requirement for the hash function h(k) is that for all values of k it should generate values between S1 and S2.

It is obvious that a hash function that maps many different key values to a single address or one that does not map the key values uniformly is a bad hash function. A collision is said to occur when two distinct key values are mapped to the same storage location. Collision is handled in a number of ways. The colliding records may be assigned to the next available space, or they may be assigned to an overflow area. We can immediately see that with hashing schemes there are no indexes to traverse. With well-designed hashing functions where collisions are few, this is a great advantage.

Another problem that we have to resolve is to decide what address is represented by h(k). Let the addresses generated by the hash function the addresses of buckets in which the y, address pair values of records are stored. Figure shows the buckets containing the y, address pairs that allow a reorganization of the actual data file and actual record address without affecting the hash functions. A limited number of collisions could be handled automatically by the use of a bucket of sufficient capacity. Obviously the space required for the buckets will be, in general, much smaller than the actual data file. Consequently, its reorganization will not be that expensive. Once the bucket address is generated from the key by the hash function, a

search in the bucket is also required to locate the address of the required record. However, since the bucket size is small, this overhead is small.

The use of the bucket reduces the problem associated with collisions. In spite of this, a bucket may become full and the resulting overflow could be handled by providing overflow buckets and using a pointer from the normal bucket to an entry in the overflow bucket. All such overflow entries are linked. Multiple overflows from the same bucket results in a long list and slows down the retrieval of these records. In an alternate scheme, the address generated by the hash function is a bucket address and the bucket is used to store the records directly instead of using a pointer to the block containing the record.

Figure 21 : Bucket and block organization for hashing

Let s represent the value:

s = upper bucket address value - lower bucket address value + 1

Here, s gives the number of buckets. Assume that we have some mechanism to convert key values to numeric ones. Then a simple hashing function is:

h(k) = k mod S

Where k is the numeric representation of the key and h(k) produces a bucket address. A moment's thought tells us that this method would perform well in some cases and not in others.

It has been shown, however, that the choice of a prime number for s is usually satisfactory. A combination of multiplicative and divisive methods can be used to advantage in many practical situations.

There are innumerable ways of converting a key to a numeric value. Most keys are numeric; others may be either alphabetic or alphanumeric. In the latter two cases, we can use the bit representation of the alphabet to generate the numeric equivalent key. A number of simple hashing methods are given below. Many hashing functions can be devised from these and other ways.

For the above key (converted to integer value if required) the end folding gives the two values to be added as: 123456654321 and 123456789012.

We can conclude from the above discussion that a number of possible methods for generating a hash function exist. In general it has been found that hash functions using division or multiplication performs quite well under most conditions.

To summarize the advantages and disadvantages of this approach:

Advantages of hashing:

1. Exact key matches are extremely quick.

4. No disk space is used by this indexing method.

Disadvantages of hashing:

2. No sorting of data occurs either physically or logically so sequential access is poor.

In this section, we have introduced a family of file organization schemes that allow records to be accessed by more than one key field. Until this point, we have considered only single-key file organization. Sequential by a given key, direct access by a particular key and indexed sequential giving both direct and sequential access by a single key. Now we enlarge our base to include those file organization that enable a single data file to support multiple access paths, each by a different key. These file organization techniques are at the heart of database implementation.

There are numerous techniques that have been used to implement multi key file organization. Most of the approaches are based on building indexes to provide direct access by key value. The fundamental indexing techniques were already introduced in the section 3.4. In this section we discuss two approaches for providing additional access paths into a file of data records.

3.6.1 Need for the Multiple Access Path

Many interactive information systems require the support of multi-key files. Consider a banking system in which there are several types of users: teller, loan officers, branch manager, bank officers, account holders, and so forth. All have the need to access the same data, say records of the format shown in figure 22 Various types of users need to access these records in different ways. A teller might identify an account record by its ID value. A loan officer might need to access all account records with a given value for OVERDRAW-LIMIT, or all account records for a given value of SOCNO. A branch manager might access records by the BRANCH and TYPE group code. A bank officer might want periodic reports of all accounts data, sorted by ID. An account holder (customer) might be able to access his or her own record by giving the appropriate ID value or a combination of NAME, SOCNO, and TYPE code.

Figure 22 : Example record format

Support by Replicating Data

One approach to being able to support all these types of access is to have several different files; each organized to serve one type of request. For this banking example, there might be one indexed sequential account file with key ID (to server tellers, bank officers, and account holders), one sequential account file with records ordered by OVER-DRAW-LIMIT (to serve loan officer), one account rile with relative organization and user-key SOCNO (to serve loan officers), one sequential account file with records ordered by GROUP-CODF- (to serve branch managers), and one relative account file, with user-key NAME, SOCNO, and TYPE code (to serve account holders). We have just identified five files, all containing the same data records! The, five files differ only in their organizations, and thus in the access paths they provide.

Difficulties Caused by Replication

Replicating data across files is not a desirable solution to the problem of providing multiple access paths through that data. One obvious difficulty with this approach is the resultant storage space requirements. However, a more serious difficulty with this approach is keeping updates to the replicated data records coordinated. The multi-key file is a classical and often successful solution to the multiple-path retrieval problem; it uses indexes rather than data replication.

Whenever multiple copies of data exist, there is the potential for discrepancies. Assume that you have three calendars. You keep one at home by the telephone, one in your briefcase, and one at your office. What is the probability that those three calendars show the same record of appointments and obligations? The likely situation is that you will post some updates to one copy but forget to enter them in other copies. Even if you are quite conscientious about updating all three copies, there must be some lag between the times that the updates actually appear in the three locations. The problem becomes more complex if somebody in addition to you, for example your secretary, also updates one or more of your calendars. The same difficulties arise in updating data that appear in multiple files.

The result of incomplete and asynchronous updates is loss of data integrity. If a loan officer queries one file and finds that account #123456 has an overdraw limit of $250, then queries another file and finds that the same account has an overdraw limit of $ 1 000, he or she should question the validity of the data.

Support by Adding Indexes

Another approach to being able to support several different kinds of access to a collection of data records is to have one data file with multiple access paths. Now there is only one copy of any data record to be updated, and the update synchronization problem caused by record duplication is avoided. This approach is called multi-key file organization.

The concept of multiple-key access generally is implemented by building multiple indexes to provide different access paths to the data records. There may also be multiple linked lists through the data records. We have seen already that an index can be structured in several ways, for example as a table, a binary search tree, a B-tree, or a B+ - tree. The most appropriate method of implementing a particular multi-key file is dependent upon the actual uses to be made of the data and the kinds of multi-key file support available.

3.6.2 Multilist file organization

Before defining multilist file organization, let us understand the difference between linked organization and sequential file organization. Linked organizations differ from sequential organizations essentially in that the logical sequence of records is generally from the physical sequence. In a sequential organization, if the i'th record of the file is at location 1i then the i + 1'st record is in the next physical position 1i + c where c may be the length of the i'th record or some constant that determines the inter-record spacing. In a linked organization the next logical record is obtained by following a link value from the present record. Linking records together in order of increasing primary key value facilitates easy insertion and deletion once the place at which the insertion or deletion to be made is known. Searching for a record with a given primary key value is difficult when no index is available, since the only search possible is a sequential search. To facilitate searching on the primary key as well as on secondary keys it is customary to maintain several indexes, one for each key. An employee number index, for instance, may contain entries corresponding to ranges of employee numbers. One possibility for the example of figure 23 would be to have an entry for each of the ranges 501-700, 701-900 and 901-1100. All records having E# in the same range will be linked together as in figure 24. Using an index in this way reduces the length of the lists and thus the search time. This idea is very easily generalized to allow for easy secondary key retrieval. We just set up indexes for each key and allow records to be in more than one list. This leads to the multilist structure for file representation. Figure 25 shows the indexes and lists corresponding to multilist representation of the data of figure 24. It is assumed that the only fields designated as keys are: E#, Occupation, Sex and Salary. Each record in the file, in addition to all the relevant information fields, has 1 link field for each key field.

Figure 23 : Sample data for Employee file

The logical order of records in any particular list may or may not be important depending upon the application. In the example file, lists corresponding to E#, Occupation and Sex have been set up in order of increasing E#. The salary lists have been set up in order of increasing salary within each range (record A precedes D and C even though E#(C) and E#(D) are less than E#(A)).

Figure 24 : Linking together all seconds in the same type

Figure 25 : Multillist representation for figure 23

Notice that in addition to key values and pointers to lists, each index entry also contains the length of the corresponding list. This information is useful when retrieval on Boolean queries is required. In order to meet a query of the type, retrieve all records with Sex = female and Occupation = analyst, we search the Sex and Occupation indexes for female and analyst respectively. This gives us the pointers B and B. The length of the list of analysts is less than that of the list of females, so the analyst list starting at B is searched. The records in this list are retrieved and the Sex key examined to determine if the record truly satisfies the query. Retaining list lengths enables us to reduce search time by allowing us to search the smaller list. Multilist structures provide a seemingly satisfactory solution for simple and range queries.

When Boolean queries are involved, the search time may bear no relation to the number of records satisfying the query. The query K I = XX and K2 = XY may lead to a XX list of length n and a K2 list of length m. Then, min ( n,m} records will be retrieved and tested against the query. It is quite possible that none or only a very small number of these min {n,m} records have both K1 = XX and K2 = XY. This situation can be remedied to some extent by the use of compound keys. A compound key is obtained by combining two or more keys together. We would combine the Sex and Occupation keys to get a new key Sex-Occupation. The values for this key would be: female analyst, female programmer, male analyst and male programmer. With this compound key replacing the two keys Sex and Occupation, we can satisfy queries of the type, all male programmers, or all programmers, by retrieving only as many records as actually satisfy the query. The index size, however, grows rapidly with key compounding. If we have ten keys K1, ---- K10, the index for Ki having ni entries, then the index for the compound key K1- K2 ...... K10 will have P10 i=10 ni entries while the original indexes, had a total of å 10 i=10 ni entries. Also, handling simple queries becomes more complex if the individual key indexes are no longer retained.

Inserting a new record into a multilist structure is easy so long as the individual lists do not have to be maintained in some order. In this case the record may be inserted at the front of the appropriate lists. Deletion of a record is difficult since there are no back pointers. Deletion may be simplified at the expense of doubling the number of link fields and maintaining each list as a doubly linked list. When space is at a premium, this expense may not be acceptable. An alternative is the coral ring structure described below.

3.6.3 Inverted File Organization

Conceptually, inverted files are similar to multilists. The difference is that while in multilists records with the same key value are linked together with link information being kept in individual records, in the case of inverted files this link information is kept in the index itself. Figure 27 shows the indexes for the file of figure 24. A slightly different strategy has been used in the E# and salary indexes than was used in figure 26, though the same strategy could have been used here too.

To simplify further discussion, we shall assume that the index for every key is dense and contains a value entry for each distinct value in the file. Since the index entries are variable length (the number of records with the same key value is variable), index maintenance becomes more complex than for multilist. However, several benefits accrue from this scheme. Boolean queries require only one access per record satisfying the query (plus some accesses to process the indexes). Queries of the type K1 = XX and K2 = XY. These two lists are then merged to obtain a list of all records satisfying the query. K1 = XX and K2 = XY can be handled similarly by intersecting the two lists. K1 =.not. XX can be handled by maintaining a universal list, U, with the addresses of all records. Then, K1 = .not. XX is just the difference between U and the list for K1 = Y-X. Any complex Boolean query may be handled in this way. The retrieval works in two steps. In the first step, the indexes are processed to obtain a list of records satisfying the query and in the second, these records are retrieved using this list. The number of disk accesses needed is equal to the number of records being retrieved plus the number to process the indexes.

Inverted files represent one extreme of file organization in which only the index structures are important. The records themselves may be stored in any way (sequentially ordered by primary key, random, linked ordered by primary key etc.).

Figure 27 : Indexes for fully inverted file

Inverted files may also result in space saving compared with other file structures when record retrieval does not require retrieval of key fields. In this case, the key fields may be deleted from the records. In the case of multilist structures, this deletion of key fields is possible only with significant loss in system retrieval performance. Insertion and deletion of records requires only the ability to insert and delete within indexes.

3.6.4 Comparison and Tradeoff in the Design of Multikey File

Both inverted files and multi-list files have

· In either file organization

· The indexes differ in that

· Thus an inversion index may have variable-length entries whereas a multi-list index has fixed-length entries. In either organization

· Some of the implications of these differences are the following:

Check Your Progress

1. What is the different between Clustering and Indexing?

2. Why hashing is required in direct file organisation?

In this unit, we discussed four fundamental file organization techniques. These are sequential, indexed sequential, direct, and multi-key file organization. The selection of the appropriate organization for a file in an information system is important to the performance of that system. The fundamental factors that influence the selection process include the following:

1.Nature of operation to be performed.

2.Characteristics of storage media to be used.

3. Volume and frequency of transaction to be processed.

4. Response time requirement.

1. In a B+ tree the leaves are linked together to form a sequence set; interior nodes exist only for the purposes of indexing the sequence set (not to index into data/records). The insertion and deletion algorithm differ slightly.

2. Sequential access to the keys of a B-tree is much slower than sequential access to the keys of a B+ tree, since the latter are linked in sequential order by definition.

1. Bipin C. Desai, An Introduction to Database Systems, Galgotia Publication Pvt. Ltd. New Delhi, 1994
2. Mary E. S. Loomis, Data Management and File Structures (Second Edition) PHI.
3. Horowtz & Sahni, Fundamentals of data Structure, New Delhi.