I want to implement an Index using a B+Tree as the underlying data structure. The index will have to support key sizes which are of order of my block size, what means I cannot save all the key as a pivot in the B+Tree inner nodes, since the branching factor would be too small which results in too many IOS for any read/write operation, as the B+Tree will be significantly high. Moreover, I wish to preserve key's order, what means that compression methods which does not preserve order cannot work for me without adjustments. I am looking for papers which talks about it and related issues. In addition if you have tackled this problem before, I would be glad to accept any suggestions and ideas. Also I wish to use a B+Tree, I am open for any other data-structure which might be more appropriate for this task.
1 Answer
Note: In what follows, I'm going to use the term "B-tree" to refer to the general idea of B-trees regardless of the variant, and "B+-trees" to refer specifically to B+-trees.
You've correctly identified a real-word complication of using B-trees to index strings: B-trees are page-structured files, but strings are of arbitrary length. This is glossed over in most tutorials and textbooks, but it's a real issue.
Most theoretical presentations of B-trees talk in terms of fixed fanouts, but in practice, the fanout of a node is partly determined by the sizes of the keys. If the keys are physically smaller, you can store more pointers in the node.
For this reason, many (probably most) database systems impose an upper limit on the size of a key that can be stored in a node. Say you're using 64kB pages/blocks, then you might require that no key can take up more than 8kB in a node. This gives you a minimum fanout of 8 for a B+-tree inner node (remember that if there are n pointers out of a node, you only need to store n-1 keys).
The simplest (and likely the most common) realisation of this idea means that the index is only "fast" on the first 8kB of a string, and the index lookup devolves to some other algorithm (e.g. linear or binary search) if there are too many records whose keys are distinct, but not distinguished by their first 8kB.
For a general-purpose DBMS, this is probably the right thing to do. The meaning of a query is still correct because the "real" keys are present in the records, and the system doesn't spend a lot of complexity on an uncommon case.
Even relatively inexperienced database designers know what B-tree string indexes are good for, and indexing a whole XML document as a string is not that. If someone ever does it, whether on purpose or by accident, the DBMS will still return the correct answer, but it will just degenerate to a less-efficient algorithm, and probably also signal to the database administrator that there are a significant number of inefficient queries occurring and perhaps they should take a look.
This is why the problem hasn't historically received a lot of attention.
OK, but let's assume you're not doing that. Your database is not general-purpose, and you have an excellent reason to want to index long strings. What to do?
If the key size is really roughly the same as the page size, this suggests a simple solution: make the page size bigger. Page size doesn't matter as much as it once did, since virtual address spaces are so much bigger than file sizes. Plus, you get a read-ahead bonus on modern operating systems if you read part of a file sequentially. So simply using bigger pages may not be as bad as you think if you need a quick and dirty solution.
But even if virtual memory space is essentially free, RAM and cache are not, so it's worth trying to be smart about it.
A few observations:
- You don't need to store "real" keys in a B+-tree internal node. You only need a value which is guaranteed to be "between" all of the keys in two child subtrees.
- If you have long keys, you don't want to be comparing whole keys all the time, and indeed you probably aren't. The further down you go in the tree, the more likely it is that all of the keys in the subtree share a (long?) prefix. You don't want to store, or compare, that prefix in every place where a key needs to be stored.
You see, most of the time, you'll find yourself in one of two situations: either the set of keys in the index that you're considering don't have a long common prefix, in which case you should be able to compare the first portion of the keys only, or they do have a long common prefix, in which case you shouldn't need to compare that prefix. Moreover, that prefix should only need to be stored once for all keys in the subtree.
This suggests that what you probably want is something more like a trie. Perhaps unsurprisingly, there are data structures that do this, such as prefix B-trees and B-tries (which are basically burst tries stored on disk).
I recommend you read those papers, but I'll try to give you some ideas about the design space here.
Suppose that all keys under a given node have a common prefix. Then within a node, you only need to store the "distinguishing" parts.
Think about the "internal" representation of a B+-tree node. The way that B+-trees are usually presented is that internal nodes are an array of n-1 keys and an array of n pointers, and you use binary search on the keys to find which pointer to traverse.
Arrays-with-binary-search are only one possibility, and you could in theory pack any search data structure that you want within a node. There's no reason why you couldn't use something more like a trie for the node representation.
If you do find yourself with a highly lopsided node in your B+-tree, say where one key is different in its first character, but all of the others have an 8kB prefix in common, you could use that to inform the balancing policy. Perhaps that one key could be moved into a sibling node? Even if that results in the sibling node splitting, that could be preferable than the alternative.
You also may have to live with using a different balance condition for your tree as a whole, such as the fanout for each node depending on key distribution, or the distance from the root not being the same for all leaves.
Consider the possibility, for example, of a B+-tree node with only one child pointer, with the rest of the node simply serving the purpose of storing "common prefix" for all child keys. You could think of this as inserting an extra "level" in the node where needed, or you could think of that node and its child as being one logical node that just happens to be larger than a page in size so that more key material can be stored. Is this a distinction without a difference?
If you're worried about complexity... well, yes, you would like $O(\log n)$ I/O operations where $n$ is the number of nodes, but if keys are huge, there is no way (compression notwithstanding) to get around doing $O(\frac{s}{p})$ I/O operations where $s$ is the size of the key and $p$ is the page size. We usually don't consider that when analysing B-trees, but that may dominate in your application.
Good luck!
