Sparse dictionary tree
Techniques related to a sparse dictionary tree are disclosed. In some embodiments, computing device(s) execute instructions, which are stored on non-transitory storage media, for performing a method. The method comprises storing an encoding dictionary as a token-ordered tree comprising a first node and a second node, which are adjacent nodes. The token-ordered tree maps ordered tokens to ordered codes. The ordered tokens include a first token and a second token. The ordered codes include a first code and a second code, which are non-consecutive codes. The first node maps the first token to the first code. The second node maps the second token to the second code. The encoding dictionary is updated based on inserting a third node between the first node and the second node. The third node maps a third token to a third code that is greater than the first code and less than the second code.
1. A method comprising:
storing, as a token-ordered tree, an encoding dictionary that maps a plurality of ordered tokens to a subset of a plurality of ordered codes, wherein a pair of adjacent nodes of said token-ordered tree comprises a first node and a second node, wherein said first node maps a first token of said plurality of ordered tokens to a first code of said plurality of ordered codes, wherein said second node maps a second token of said plurality of ordered tokens to a second code of said plurality of ordered codes, and wherein said first code and said second code are non-consecutive codes;
updating said encoding dictionary based on inserting a third node between said first node and said second node, wherein said third node maps a third token to a third code that is greater than said first code and less than said second code;
wherein said first code differs from said second code by a differential that is determined based on a difference between a cardinality of said plurality of ordered codes and a cardinality of said plurality of ordered tokens and dividing the difference by said cardinality of said plurality of ordered tokens;
wherein the method is performed by one or more computing devices.
2. The method of claim 1 , further including determiningsaid third code based on averaging said first code with said second code.
3. The method of claim 1 , wherein updating said encoding dictionary is performed at runtime based on a locking protocol that supports concurrent reads and updates.
4. The method of claim 1 , further including sharingsaid encoding dictionary across a distributed database.
5. The method of claim 1 , further comprising:
updating said encoding dictionary based on inserting a sixth node between a fourth node and a fifth node, wherein said fourth node and said fifth node correspond to consecutive codes, and wherein inserting said sixth node comprises re-encoding said fifth node to make space for said sixth node.
6. The method of claim 1 , further comprising:
deleting, from said token-ordered tree, a node having a reference counter that reaches zero.
7. The method of claim 1 , further comprising:
scanning a column of a database table for tokens that are in use;
marking all nodes of said token-ordered tree corresponding to said tokens that are in use;
deleting any unmarked nodes of said token-ordered tree.
8. The method of claim 1 , further comprising:
after updating said encoding dictionary, updating a corresponding decoding dictionary based on inserting said third token into a hash map.
9. The method of claim 8 , wherein updating said corresponding decoding dictionary is performed at runtime.
10. One or more non-transitory storage media storing one or more sequences of instructions that, when executed by one or more computing devices, cause:
storing, as a token-ordered tree, an encoding dictionary that maps a plurality of ordered tokens to a subset of a plurality of ordered codes, wherein a pair of adjacent nodes of said token-ordered tree comprises a first node and a second node, wherein said first node maps a first token of said plurality of ordered tokens to a first code of said plurality of ordered codes, wherein said second node maps a second token of said plurality of ordered tokens to a second code of said plurality of ordered codes, and wherein said first code and said second code are non-consecutive codes;
updating said encoding dictionary based on inserting a third node between said first node and said second node, wherein said third node maps a third token to a third code that is greater than said first code and less than said second code; and
wherein said first code differs from said second code by a differential that is determined based on a difference between a cardinality of said plurality of ordered codes and a cardinality of said plurality of ordered tokens and dividing the difference by said cardinality of said plurality of ordered tokens;
wherein the method is performed by one or more computing devices.
11. The one or more non-transitory storage media of claim 10 , wherein said one or more sequences of instructions include instructions that, when executed by said one or more computing devices, cause determining said third code based on averaging said first code with said second code.
12. The one or more non-transitory storage media of claim 10 , wherein said one or more sequences of instructions include instructions that, when executed by said one or more computing devices, cause updating said encoding dictionary to be performed at runtime based on a locking protocol that supports concurrent reads and updates.
13. The one or more non-transitory storage media of claim 10 , wherein said one or more sequences of instructions include instructions that, when executed by said one or more computing devices, cause sharing said encoding dictionary across a distributed database.
14. The one or more non-transitory storage media of claim 10 , wherein said one or more sequences of instructions include instructions that, when executed by said one or more computing devices, cause:
updating said encoding dictionary based on inserting a sixth node between a fourth node and a fifth node, wherein said fourth node and said fifth node correspond to consecutive codes, and wherein inserting said sixth node comprises re-encoding said fifth node to make space for said sixth node.
15. The one or more non-transitory storage media of claim 10 , wherein said one or more sequences of instructions include instructions that, when executed by said one or more computing devices, cause:
deleting, from said token-ordered tree, a node having a reference counter that reaches zero.
16. The one or more non-transitory storage media of claim 10 , wherein said one or more sequences of instructions include instructions that, when executed by said one or more computing devices, cause:
scanning a column of a database table for tokens that are in use;
marking all nodes of said token-ordered tree corresponding to said tokens that are in use;
deleting any unmarked nodes of said token-ordered tree.
17. The one or more non-transitory storage media of claim 10 , wherein said one or more sequences of instructions include instructions that, when executed by said one or more computing devices, cause:
after updating said encoding dictionary, updating a corresponding decoding dictionary based on inserting said third token into a hash map.
18. The one or more non-transitory storage media of claim 17 , wherein said one or more sequences of instructions include instructions that, when executed by said one or more computing devices cause updating said corresponding decoding dictionary to be performed at runtime.