3

I am creating a database storage engine (for fun).

I know it uses b-trees (and stuff), but in all of b-tree base examples, it shows that we need to sort keys and then store it for indexing, not for integers.

I can understand sorting, but how to do it for strings, if I have string as a key for indexing?

Ex : I want to index all email addresses in btree , how would I do that ??

00imvj00
  • 665
  • 7
  • 18
  • What do you mean by "b-tree base examples"? Do you mean "basic examples"? If you mean that, which examples exactly are you referring to? Please, edit your question to add these details. – nbro Mar 07 '17 at 15:15
  • Edited. Basically I want to create disk based btree for string , like email or name or anything. How do I perform sorting on string ? – 00imvj00 Mar 07 '17 at 15:53
  • 1
    The only thing you need is a *compare* function. That will allow *any* data type to be indexed, not only strings. And every data type will need its own compare function. (even composite types, such as records) – wildplasser Mar 07 '17 at 16:01

1 Answers1

5

It does not matter, what type of data you are sorting. For a B-Tree you only need a comparator. The first value you put into your db is the root. The second value gets compared to the root. If smaller, then continue down left, else right. Inserting new values often requires to restructure your tree.

A comparator for a string could use the length of the string or compare it alphabetically or count the dots in an email behind the at-sign.

Jemolah
  • 1,962
  • 3
  • 24
  • 41