Method for organizing directories

• US 6,208,993 B1
• Filed: 07/22/1999
• Issued: 03/27/2001
• Est. Priority Date: 07/26/1996
• Status: Expired due to Term

• Current Assignee: DB Software, Inc.
• Original Assignee: Ori Software Development Ltd
• Inventors: Shadmon, Moshe
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/358,440
• Time in Patent Office: 614 Days
• Field of Search: 707/107, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

In a database file management system for accessing data records that correspond to items in a directory. The directory items are linked to a trie index that is arranged in blocks and being stored in a storage medium. The trie index enables accessing or updating the directory items data records by key or keys and being susceptible to an unbalanced structure of blocks. There is provided a method for constructing a layered index arranged in blocks, which includes the steps of providing the trie index and constructing a representative index over the representative keys of the trie index. The layered index enables accessing or updating the directory items by key or keys and it constitutes a balanced structure of blocks.

Claims

1. In a storage medium used by a database file management system executed on data processing system, a data structure for efficient representation of hierarchical directories that includes items;

the storage medium includes;

a layered index arranged in blocks;

the layered index includes a basic partitioned index that is associated with data records standing for said items;

the basic partitioned index enables accessing or updating the data records by key or keys, and being susceptible to an unbalanced structure of blocks;

said layered index enables accessing or updating the data records by key or keys and constitutes a balanced structure of blocks.

2. The layered index of claim 1, wherein said basic partitioned index being a trie.

3. The layered index of claim 2, wherein said trie being a PAIF trie.

4. The layered index according to claim 3, wherein the layered index includes the Btree index scheme.

5. The layered index according to claim 3, wherein the layered index includes substantially the PAIF index scheme.

6. The layered index of claim 1, wherein said storage medium being an external memory.

7. The layered index of claim 6, wherein said storage medium being further an internal memory.

8. The layered index of claim 1, wherein said storage medium being an internal memory.

9. The layered index of claim 1, wherein the basic partitioned index and a representative index of said layered index being substantially the same index schemes.

10. The layered index according to claim 9, wherein the representative index being substantially a PAIF index scheme.

11. The layered index of claim 1, wherein the basic partitioned index and a representative index of said layered index being different index schemes.

12. The layered index according to claim 11, wherein the representative index being the Btree index scheme.

13. The layered index according to claim 1, capable of supporting the ODBC standard.

14. The layered index I₀, . . . , I_h according to claim 1, comprising:

a representative index I₁, . . . , I_h constructed such that any Ij is constructed over the representative keys of Ij−

1.

15. The layered index I₀, . . . , I_h according to claim 14, wherein I_h is fully contained in one block.

16. The method for accessing a sought data record r by key k in the layered index of claim 1;

the data record stands for an item in a directory;

the method comprising the steps of;

(a) searching k in I_h to I_k where h≧

k≧

0 and in the case it is not found in the key of a data record in order to find the block of I<sub>h−

1</sub> leading to k;

(b) repeating step (a) until reaching the block of I₀ that is associated with the data record with key k, if exists.

17. The method for inserting a data record r by key k in the layered index of claim 1;

the data record stands for an item in a directory;

the method comprising the steps of;

(a) searching k in I_h to I_k where h≧

k≧

0 and in the case it is not found in the key of a data record in order to find the block of I<sub>h−

1</sub> leading to k;

(b) repeating step (a) until reaching the block B of I₀ that is associated with the data record with key k, if exists;

(c) associating r to B.

18. The method for deleting a record r by key k in the layered index of claim 1;

the data record stands for an item in a directory;

the method comprising the steps of;

(a) searching k in I_h to I_k where h≧

k≧

0 and in the case it is not found in the key of a data record in order to find the block of I<sub>h−

1</sub> leading to k;

(b) repeating step (a) until reaching the block B of I₀ that is associated with the data record with key k, if exists;

(c) disconnecting r from B.

19. The storage medium of claim 1, for use in Internet application.

20. The storage medium of claim 1, for use in Intranet application.

21. The storage medium of claim 1, wherein at least one of said data records being a multidimensional data record.

22. In a storage medium used by a database file management system executed on data processing system, a data structure for efficient representation of hierarchical directories that includes items;

the storage medium includes;

an index arranged in blocks and being constructed over the keys of data records standing for said items;

the index includes a basic partitioned index that is associated with the data records;

the basic partitioned index enables accessing or updating the data records by key or keys, and being susceptible to an unbalanced structure of blocks;

said index enables accessing or updating the data records by key or keys and constitutes a balanced structure of blocks.

23. In a storage medium used by a database file management system executed on data processing system, a data structure for efficient representation of hierarchical directories that includes items;

the storage medium includes;

an index arranged in blocks and being constructed over the keys of data records standing for said items;

the index includes a trie that is associated with the data records;

the trie enables accessing or updating the data records by key or keys, and being susceptible to an unbalanced structure of blocks;

said index enables accessing or updating the data records by key or keys and constitutes a balanced structure of blocks.

24. In a database file management system for accessing data records, and being executed on data processing system;

the data records are associated with a basic partitioned index arranged in blocks and being stored in a storage medium;

the basic partitioned index enables accessing or updating the data records by key or keys and being susceptible to an unbalanced structure of blocks;

a method for constructing a layered index arranged in blocks, comprising the steps of;

(a) providing said basic partitioned index;

(b) constructing a representative index over the representative keys of said basic partitioned index;

said layered index enables accessing or updating the data records that stand for items of a directory by key or keys and constitutes a balanced structure of blocks.

25. The layered index of claim 24 wherein said basic partitioned index being a trie.

26. The method of claim 25, wherein said trie being a PAIF trie.

27. The method of claim 24, wherein the basic partitioned index and the representative index being substantially the same index schemes.

28. The method of claim 24, wherein the basic partitioned index and the representative index being different index schemes.

29. The method of claim 28, wherein the representative index being a Btree index scheme.

30. The layered index according to claim 28, wherein the representative index being a PAIF index scheme.

31. The method of claim 24, wherein said index supports sequential operations.

32. The method of claim 24, wherein said constructing step (b) includes:

(a) if B (in I<sub>k−

1</sub>) overflows, it is split into two (or more) blocks and the representative of B in I_h is replaced by the representatives of the new blocks;

(b) if the block of I_h overflows an additional layer I_h+1 is created and added to the layered index.

33. The method according to claim 24, wherein the constructing step (b) includes:

(a) at least one short link among the short links of a node (hereon split node) in the block (of B<sub>i−

1</sub>) is deleted (hereon split link) in a way that at least two tries exist in the block;

(b) each of the sub-trees is moved to a separate block;

(c) if the block of B_i does not exist, B_i is created and a copied node of the split node is created in B_i;

(d) if the block of B_i exists and a copied node of the split node does not exist in B_i, then a copied node of the split node is created in B_i and connected to the trie of B_i such that B<sub>i−

1</sub>′

(at the end of the split process) is accessible in a search path that includes the root node in B_i and the copied note and its labeled links according to the representative key of B<sub>i−

1</sub>′

;

(e) if the copied note has no direct link, a direct link is added from the copied node to the block B<sub>i−

1</sub>;

(f) a far link added from the copied node to the block B<sub>i−

1</sub>′

or if the copied node has a short link to a child node in the direction of the far link, the far link is replaced by a direct link from the child node to block B<sub>i−

1</sub>′

.

34. In a database file management system for accessing data records and being executed on data processing system;

the data records are associated with a basic partitioned index arranged in blocks and being stored in a storage medium;

the basic partitioned index enables accessing or updating the data records by key or keys and being susceptible to an unbalanced structure of blocks;

a method for constructing an index over the keys of the data records, the index being arranged in blocks, comprising the steps of;

(a) providing said basic partitioned index;

(b) constructing an index over representative keys of said basic partitioned index;

said index enables accessing or updating the data records that stand for items of a directory by key or keys and constitutes a balanced structure of blocks.

35. In a database file management system for accessing data records and being executed on data processing system;

the data records are associated with a trie arranged in blocks and being stored in a storage medium;

the trie enables accessing or updating the data records by key or keys and being susceptible to an unbalanced structure of blocks;

a method for constructing an index over the keys of the data records, the index being arranged in blocks, comprising the steps of;

(a) providing a trie;

(b) constructing an index over the representative keys of said trie;

said index enables accessing or updating the data records that stand for items of a directory by key or keys and constitutes a balanced structure of blocks.

36. In a storage medium used by a database file management system executed on data processing system, a data structure that includes at least one probablistic access indexing file (PAIF) having a plurality of nodes and links;

the leaf nodes of said PAIF are associated each with at least one data record standing for respective at least one directory of an item, accessible to said user application program and wherein at least portion of said data record constitutes at least one search-key;

selected nodes in said PAIF represent, each, a given offset of a search key portion within said search key;

link(s) originated from each given node from among said selected nodes, represent, each, a unique value of said search key portion;

the PAIF having at least two sub-PAIF'"'"'s being arranged, each, in a block;

said data base file management system is further capable of arranging said blocks as a balanced structure of blocks.

37. A method for inserting a new data record standing for an item of a directory into an existing PAIF according to claim 36 including the execution of the following steps:

i. advancing along a reference path commencing from the root node and ending at a data record associated to a leaf node (referred to as “

reference data record”

);

in each node in the reference path, advancing along a link originated from said node if the value represented by the link equals the value of the 1-bit-long key portion at the offset specified by said node;

in the case that the offset specified in the node is beyond any corresponding key portion in the key, or if there is no link with said value, advancing along an arbitrary path to any reference data record;

ii. comparing the search key of the reference data record to that of the new data record for determining the smallest offset of the search key portion that discerns the two (hereinafter discerning offset);

iii. proceed to one of the following steps (iii.0-iii.3) depending upon the value of the discerning offset;

iii.0 if the data records are equal then terminate;

or

iii.1 if the discerning offset matches the offset indicated by one of the nodes in the reference path, add another link originating from said one node and assign to said link the value of the search key portion at the discerning offset taken from the search key of the new data record;

or

iii.2 if the discerning offset is larger than that indicated by the leaf node that is linked, by means of a link, to the reference data record;

iii.2.1 disconnect the link from the reference data record (i.e. it remains temporarily “

loose”

) and move the link to a new node;

the new node is assigned with a value of the discerning offset;

iii.2.2 connect the reference data record and the new node (which now becomes a leaf node) and assign to the link (long link) a value of the search-key-portion at the discerning offset taken from the search key of the reference data record;

iii.2.3 connect by means of a link the new data record and the new node and assign to the link (long link) a value of the search-key-portion at the discerning offset taken from the search key of the new data record;

or

iii.3 if conditions iii.0, iii.1 and iii.2 are not met, there exists, in the reference search path, a father node and a child node thereof such that the discerning offset is, at the same time, larger than the offset assigned to the father node and smaller than the offset assigned to the child node - (- considered case A), or all the nodes in the reference search path have a value greater than the discerning offset - (- considered case B);

accordingly, apply the following sub-steps;

iii.3.1 for case A and B, create a new node and assign the node with the value of said discerning offset, for case A only—

disconnect the link from the father node to the child node and shift the link to a new internal node (i.e. the child node remains temporarily “

loose”

);

iii.3.2 for case A and B, connect by means of a link (long link) the new data record and said new internal node;

the value assigned to the link is that of the search-key-portion at the discerning offset, as taken from the search key of the new data record;

iii.3.3 for case A and B, connect by means of a new link the new node and for case A—

the child node, for case B—

the root node (i.e. the new node becomes for case A—

a new father node, for case B—

a new root node), and the value assigned to said link is the search-key-portion at the offset indicated by the new node, taken from the search key of the reference data record.

38. In a computer system having a storage medium of at least an internal memory that ranges between 10 to 20 M byte or more, and an external memory;

a data structure that includes an index over the keys of the data records that stand for items of a directory;

the index is arranged in blocks;

such that for one billion data records substantially no more than two accesses to said external memory are required in order to access a block that is associated with any one of said billion data records, irrespective of the size of the key of said data records.

39. In a computer system having a storage medium of at least an internal memory that ranges between 10 to 20 M byte or more, and an external memory;

a data structure that includes an index over the keys of the data records that stand for items of a directory;

the index is arranged in blocks;

such that for one million data records substantially all the blocks of the index are accommodated in said internal memory regardless of the size of the key of said data records.

40. In a computer system having a storage medium,

a data structure that includes an index over the keys of data records that stand for items of a directory;

the index is arranged in a balanced structure of blocks and enables to perform sequential operations on said data records;

the index size is essentially not affected from the size of said keys.

41. In a storage medium used by a database file management system executed on data processing system, a data structure that includes:

an index over the keys of data records that stand for items of a directory;

the data records being of at least two types where data records of the second type are subordinated to the data records of the first type.

42. In a storage medium used by a database file management system executed on data processing system, a data structure that includes:

a designated index over designated keys of data records that stand for items of a directory;

the data records, constituting designated data records, being of at least two types where designated data records of the second type are subordinated to the designated data records of the first type.