CODEWITHSUNDEEP
databaseindexing
Zoran
Zoran

Reputation: 459

db index file implementation

I am experimenting with the design of a database index file consisting of fixed size pages each of which holds a collection of (key,pointer) records pointing to the actual data file.

Page-based design complicates everything. The most naive approach seemed to me that I should keep the records in sorted order (i.e. sorted physically like Page0 has records 0 1 3 6, Page1 has records, 7 8 12 15, ... etc) but still I cannot use e.g. binary search on the sorted file since records are not sequential but reside in pages (which have page headers, free space etc).

Could anyone offer some guidance on how to seek a fully sorted index file with pages using binary search?

edit: a page-based btree implementation is too complicated for me right now. I want to get there though after achieving simpler approaches like above.

Upvotes: 2

Views: 1160

Answers (3)

Zoran
Zoran

Reputation: 459

I later managed to do this easily.

Read the page in the middle. Check its first and last records (or records with the smallest/highest index if the page is not sorted internally). Go right or left depending on your search key. Loop.

Upvotes: 1

Tom Kerr
Tom Kerr

Reputation: 10720

The simplest thing is generally to build up the index you want to use and just keep it in memory. That way you can optimize your data storage and access apart from how it is indexed.

When I implemented something similar I saved the index as a big chunk in the file, then put the data as another bigger chunk.

Upvotes: 0

Carl Krig
Carl Krig

Reputation: 181

B-tree from wikipedia

Upvotes: 0

Related Questions