Changes between Version 4 and Version 5 of auth_backend_tree

Oct 20, 2010, 1:53:07 PM (7 years ago)



  • auth_backend_tree

    v4 v5  
    1818The image shows only part of the tree and has one big node „zoomed“. Both big and red ones would have bigger fan-out in reality and would be more of them inside one big.
    20 [[Image(dual_tree.svg)]]
    2222== Pointers ==
    3232The string data to compare must be inside the nodes. But, as they are short, only parts of it should be there (since when we are somewhere down the tree, we already checked part of it). There are two possibilities with the keys. Either they mark edges (eg. trie) or they mark separators in the tree. For simplicity, it makes no sense to mix these two inside the same node (so this should be a node-level flag). The trie ones clearly mark what is already checked, the separator ones just split the possibilities to lower nodes, without really checking anything in their name (eg. with trie, the prefix must match, with separator, it must be in between them). Maybe better showed with an image. The gray labels are labes that live there, black ones are the ones actually stored (again, the tree is not complete, we are not sure we really found what we were looking with this information). The left side is trie approach and when we get to the left node (after following the „a“ edge), we no longer need to check the first character.
    34 [[Image(trie_separator.svg)]]
    3636The use for the separator ones is at places where it is „dense“ (we will not fit the whole alphabet into single node).
    3838Now, what needs to be stored inside the node? Some flags („I'm a trie vertex“ or „I have a data pointer, to some RR sets“), some strings (of varying lengths, but no length should be longer than the node itself, so 4 or 5 bits per length should be enough) and some pointers (of various types ‒ local indices, offset 2byte ones, full-length ones). It makes sense to squash all the bit arrays together so space is not wasted. Then the string data would go. Since pointers must be alligned, they would fit from the end ‒ full-length ones at the rear, 2byte ones before them, single byte indices before. So it would look like this (bits are blue, strings yellow and pointers red):
    40 [[Image(node.svg)]]
    4242== Updates ==
    4848If we fail to allocate space inside the same big node, we need to split the big node (in a b-tree-like way). So we split its root into two small nodes, put each one into a separate big node and move the descendants to according big node.
    50 [[Image(split.svg)]]