Architecture and method to bulk load efficiently Patricia Tri

摘要

An apparatus and method for efficient bulk-loading of PATRICIA tries is disclosed. The trie is converted to its persistent representation prior to being written to an index block. Four arrays are used in the process of this conversion: a first is array used for the value nodes, a second array used for the inner nodes constituting a point-of-difference, a third array is used for storing parent pointers, and a fourth array is used for storing the running size of sub-tries. While creating the index nodes, the indexing system continuously attempts to determine the boundaries of the finished sub-tries. It also attempts to find the largest finished sub-trie that fits into a given size index block and, upon finding one, creates the persistent representation of the sub-trie and writes it into the index block.