| 摘要 |
A method, system and computer program product for dynamically adjusting node sizes in a multiway trie data structure. Upon inserting a key/value pair in a node in a multiway trie data structure that causes the number of entries in the multiway trie data structure to exceed a threshold, a splitting method is implemented. The splitting method involves doubling the width of the node in the multiway trie data structure thereby resizing the node in a resized multiway trie data structure. Furthermore, a sub-node of the original node may be split into two sections and stored in two child level nodes of the resized node under certain circumstances. Hence, only the original node and its direct successors are resized. Such a data structure outperforms hash tables by taking advantage of patterns found in the key distribution to optimize both storage requirements and access speed. |
