Allocating storage in hierarchical data bases using traces

摘要

This paper describes a class of methods to allocate a hierarchical (i.e. tree structured) data base using traces. A trace is an n-tuple of indices, [x(1),…, x(n)], which describes the unique path from the root of the tree to the node being addressed. That is, one takes the x(1)-th branch from the root, followed by the (2)-th branch from the next node, etc. until the path is completed. The last node on the path is the one being addressed.Given a set of traces that represent a set of nodes in a tree, the problem is to allocate them efficiently on a file.We approach the problem by finding ways of mapping n-tuples (i.e. traces) onto natural numbers (i.e. file indices). An allocation scheme is proposed which uses a 1:1, onto trace-to-address map and is designed to adapt to a changing distribution of nodes within the tree. The scheme is an attempt to solve the problem of efficiently allocating growing data bases.