CODEWITHSUNDEEP
algorithmtreeb-tree
chopper draw lion4
chopper draw lion4

Reputation: 13487

Searching for multiple records in a B-tree at once

Is it possible to create an implementation for a B-tree that would enable a user to search for multiple items at once? For example, if I have a B-tree that consist of names, and I input the letters "to" it would output all the names that began with "to", such as: "Tom", "Tony", "Tosh".

Upvotes: 0

Views: 49

Answers (1)

rici
rici

Reputation: 241731

Sure. A B-Tree is sorted, so you can find the first element whose value is lexicographically greater than or equal to the prefix, and then simply iterate sequentially until you find an element which does not start with the prefix.

If you want to find elements starting with a case-insensitive prefix, you'll need to adapt that algorithm. One possibility is to generate all the possible case variants of the prefix (in the case of to, there are only four, but longer prefix will have a lot more). Another possibility is to sort the B-Tree with a collation order in which different cases of the same string are adjacent; that will slow down B-Tree operations but it has the advantage of allowing case-insensitive lookups.

Upvotes: 1

Related Questions