Multi Key Organization [Data Structures]

This technique is used to sort a file based on multiple key values. Multi key file organization allows access to a data file by several different key fields. Example: Library file that requires access by author and by subject matter and title.

Scenario 1 can be like, sort the file based on roll number (this is key; you can also create clustered index). On an attribute may be other than roll number e.g. Class (MCA-I, MCA-II, MCA-III, …., MCA-VI) invert the file. 

Now if I wish to access the records of students from MCA-VI, I will locate the first record and will go sequentially in the linked list. This technique works great if -

• Attribute on which I am inverting is primary key or having nearly unique values
• The need is to access everybody in a particular class

Longer the list, it is going to be a clumsy scan. The list can be flexible in size.

• Selection/Search – go in a particular order;
• Insertion – will be easy in append mode;
• Deletion – 1) Re-arrange pointer     2) Mark deleted & re-arrange pointer at later point of time.

Scenario 2, records are sorted based on Roll numbers; now requirement is to get names of students starting with ‘J’. Therefore create inverted index on names where names starting with each alphabet will be stored as linked list. Now go through the linked list of ‘J’ to get all the records.