CODEWITHSUNDEEP
data-structuresb-tree
neuromancer
neuromancer

Reputation: 55479

Secondary keys in a B-tree

Let's say that there is a file that contains an unsorted list of student information, which includes a student ID number as well as other information.

I want to make a program that retrieves student information based on student ID number. In order to make it efficient, I store the student IDs in a B-tree.

So when I enter a student ID number, it searches the B-tree to see if its there or not. It also does one more thing. If it finds the student ID number, then it also returns where in the file that student's information is. This is the secondary key. The program uses this information to locate the rest of the student's information and prints it to screen.

Can this be done? Is this how a b-tree works?

Upvotes: 0

Views: 1063

Answers (3)

nikosdi
nikosdi

Reputation: 2158

B-Tree is an index.With a B-tree you can find values very efficient using the index.The index itself has nodes and leafs.Each node has in order to organize the content of the tree.Node pointers are pointing to other nodes or leafs. So Nodes are holding some values and some pointers.Node pointers are offsets which are reffering to the index file.The leafs also contain values,and pointers .The difference is that pointers in a leaf are an offset of the Data-File and pointing the real file.

So when you are searching for a value you are using your index in order to return to you the file offset where the real record is stored.For example you are looking for the record with ID=1, you get the offset 10240,then you open the data-file to read the block 10 if you have 1KB blocks.Then from this offset you have access to all the data off the record for example Username!

An another implementation is to use BTrees where Leafs are not pointing to an other file but they just hold a second colunum.For example If you need to find Username using ids you can have a B Tree where leafs have the following structure: the first value is the id and the second is the username so you can get the username from the index.

You can also use a B+ Tree.B+ Trees are implemented like B Trees but they are holding the leafs in a list.So you can Use your index for opperators like >,<.

Upvotes: 0

Michael Borgwardt
Michael Borgwardt

Reputation: 346260

What you describe has nothing to do with B-trees in particular (BTW, are you sure you understand what a B-tree is? Many people confuse them with binary trees), and the file position is not a "secondary key", it's a value that the student ID maps to.

However, it is true that relational databases internally work in a way quite similar to what you describe - database records are stored wherever there's free space, and indexes map values from the indexed column to the location of the record.

Upvotes: 1

Marcelo Cantos
Marcelo Cantos

Reputation: 185842

A B-tree works by storing values against keys, and allowing you to find a given key and its associated value in logarithmic time. So the second thing isn't called a secondary key, it's just the value. In this case, it's an offset into a file, which makes it essentially a pointer to the value.

This is a perfectly reasonable and very common way to use a B-tree.

Upvotes: 1

Related Questions