Slide 13.2: Indexing demonstration

Slide 13.1: Indexing
Slide 13.3: Indexing demonstration (cont.)
Home

Indexing Demonstration

The following slides demonstrate the use of an index, and the system has the following features:

An index is sorted, whereas the data file is not.

If the index entries are substantially smaller than the data file records, sorting and maintaining the index can be less expensive than sorting and maintaining the data file.

The data file is entry sequenced, which means that the record occur in the order they are entered into the file. The use of an entry-sequenced file can make record addition and file maintenance much simpler than the case with a data file that is kept sorted by a key.

The example below shows a variable-length record file books.txt (right) and its corresponding index index.txt (left) used by the system.

10    17   
0201874016|0    
0471135852|436  
0471393073|210  
0521797561|512  
0596001436|174  
0596002920|122  
0672319462|293  
1565929470|76   
1591403456|353  
1930110081|549

File Structures: An Object-Oriented Approach with C++|0201874016|94.80|360|
Learning WML & WMLScript|1565929470|17.48|12|
XML in a Nutshell, 2nd Edition|0596002920|39.95|39|
Java and XSLT|0596001436|26.37|890|
WAP Servlets: Developing Dynamic Web Content With Java and WML|0471393073|32.99|4|
WAP Development with WML and WMLScript|0672319462|18.99|56|
Advances in Security and Payment Methods for Mobile Commerce|1591403456|89.95|182|
M Commerce: Technologies, Services, and Business Models|0471135852|23.09|5|
Mobile Commerce|0521797561|29.51|93|
Dynamic WAP Application Development|1930110081|34.59|18|

The data file contains four fields: title, ISBN, price, and quantity. It uses a field delimiter ‘|’ and its key is the field ISBN. The index is with the following format:

The first two integers are: record number and record length. This line takes 12 bytes: 5 for number, 1 for space between them, 5 for length, and one for a newline.

Each of the remaining records includes two columns: key and record offset, delimited by a ‘|’. Each record takes 17 bytes: 10 for ISBN, 1 for ‘|’, 5 for offset, and one for a newline.