Alibaba Group Holding Limited
TREE PARTITIONING OF THE SUCCINCT TRIE

Abstract:

The present disclosure provides a method comprising receiving an instruction to partition a trie in a database, wherein the trie comprises a first sequence of values comprising information that indicates labels of keys in the trie, a second sequence of values comprising information that indicates whether the labels in the first sequence have one or more child nodes, a third sequence of values comprising information that indicates whether the labels in the first sequence are first child nodes under a parent node, and a fourth sequence of values comprising information that indicates values that corresponds to the labels in the first sequence; separating a sub-trie from the trie by removing entries corresponding to the sub-trie from the first, the second, the third, and the fourth sequences; and updating an entry in the fourth sequence corresponding to a parent node of the sub-trie using a memory address of the sub-trie.