Turbo Pascal database program HELP

[seltsammacker1]

Let's say I've decided my database program should store the records in a BST. Now, if I wanted to allow the user to edit data in individual entries, how would I do it? I'm stuck because the nodes in a BST aren't indexed like in an array but I don't want to use an array, so how would I locate the exact entry that the user wants to edit?

And if you think a BST isn't a good data structure for this program, then can it be done with linked list(s)? If so, how?

Thanks, any help or suggestion is appreciated.

[Cervantes]

If this is truly a database, you probably won't be storing your data in an array or linked list or BST type structure. The reason being that those are stored in the RAM, and if your database is huge, it just won't fit nicely.

Thus, your database will be stored in file(s). Chances are, this file will look and behave sort of like a linked list, where each line is an element and you can only move forwards through the lines of the file. Although you could also use some seek and tell tandem type tricks to make your file more like a BST.

So, you have a linked list or binary search tree of sorts. The only way to edit a certain entry is to search for it first. But this is akin to what you'd be doing with an array, is it not? The user wants to search for an entry starting with "Bob", so you search through your array. Similarly, you must search through your LL or BST.

The only difference between an array approach and a BST or LL approach is that it's slightly more difficult to say, "I want to edit user #325". But who ever wants to do that?

[seltsammacker1]

So you're saying that whenever the user edits the database, whatever that was edited would be written directly to a file instead of through an intermediary storage like a BST? Would it make sense tho if I inserted the records from the file into a BST for BST's sorting and searching capability?

You also said that in order to edit individual entries, a search has to be done first. Assuming I'm using a BST for the search, and there are multiples of the same key data, how would I distinguish the one entry that the user wants to edit? Would I have to go with linear search in this case and abandon using a BST? But even then, I still don't know which exact entry the user wants to edit...

Please help, Thanks!!

[Cervantes]

You can still do a binary search algorithm on your file. Sort the data in your file by whatever key (say, last name). Then determine the position of the middle line, the 1/4 and 3/4 lines, then 1/8, 3/8, 5/8, and 7/8 lines, etc. You could do this with math (assuming each line contains the same number of bytes) or by giving the file a run through. You can then use these key lines to do a binary search of sorts.

If your database is too large, you simply won't be able to store it all in RAM in a BST.

As for searching: If more than one entry exists that matches the search, you have to return a list of the matching entries. The user would then pick which one out of the list they want.
This does not rule out using a LL or BST, however. For a LL, you just go through each one and determine whether it matches. If it's does, add it to the list. For a BST, you go through as you normally would and search for the key. Then when you find it add it to the list and then search one position on either side of it. If either of those also match the key, add the appropriate one(s) to the list and then search beyond the appropriate side(s) again. Repeat this process until you find an entry that doesn't match the search request or until you reach the end of the BST.