Layered index with a basic unbalanced partitioned index that allows a balanced structure of blocks

• US 6,175,835 B1
• Filed: 01/22/1999
• Issued: 01/16/2001
• Est. Priority Date: 07/26/1996
• Status: Expired due to Term

• Current Assignee: Ori Software Development Ltd
• Original Assignee: Ori Software Development Ltd
• Inventors: Shadmon, Moshe
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/235,645
• Time in Patent Office: 725 Days
• Field of Search: 707/102
• US Class Current: 707/696
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• 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 and being executed on data processing system. The data records 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 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 data records 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 that includes:

a layered index arranged in blocks;

the layered index includes a basic partitioned index that is associated with 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 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 the 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, comprising:

(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, comprising:

(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 data record r by key k in the layered index of claim 1, comprising:

(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.

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

an index being stored in a storage medium and constructed over the keys of said data records that are stored in blocks;

the index being arranged in blocks with the leaf blocks being linked to data records by means of links;

said index is characterized in that at least one of said links is shared by at least two data records stored in the same block;

said index constituting a layered index according to claim 1, and blocks of said basic partitioned index are linked to said data records.

98. The storage medium of claim 97, wherein said index being constituted by a trie.

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

an index arranged in blocks and being constructed over the keys of data records;

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.

20. The layered index of claim 19, wherein said storage medium being an external memory.

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

22. The layered index of claim 19, wherein said storage medium being an internal memory.

23. The layered index according to claim 19, capable of supporting the ODBC standard.

24. The method for accessing a sought data record r by key k in the layered index of claim 19, comprising:

(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.

25. The method for inserting a data record r by key k in the layered index of claim 19, comprising:

(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.

26. The method for deleting a data record r by key k in the layered index of claim 19, comprising:

(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.

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

an index arranged in blocks and being constructed over the keys of data records;

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.

28. The layered index of claim 27, wherein said storage medium being an external memory.

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

30. The layered index of claim 27, wherein said storage medium being an internal memory.

31. The layered index according to claim 27, capable of supporting the ODBC standard.

32. 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 a representative keys of said basic partitioned index;

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

33. The layered index of claim 32, wherein said basic partitioned index being a trie.

34. The method of claim 33, wherein said trie being a PAIF trie.

35. The method of claim 34, wherein the representative index being the Btree index scheme.

36. The layered index according to claim 34, wherein the representative index being the PAIF index scheme.

37. The method of claim 32, wherein said storage medium being an external memory.

38. The method of claim 37, wherein said storage medium being further an internal memory.

39. The method of claim 32, wherein said storage medium being an internal memory.

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

41. The layered index according to claim 40, wherein the representative index being the PAIF index scheme.

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

43. The method of claim 42, wherein the representative index being the Btree index scheme.

44. The method of claim 32, capable of supporting the ODBC standard.

45. The method of claim 32, wherein said construction step (b) includes:

(a) If B (in I<sub>h−

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.

46. The method according to claim 45, performed on the fly.

47. The method according to claim 45, performed post factum.

48. The method according to claim 32, 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 node and its labeled links according to the representative key of B<sub>i−

1</sub>′

;

(e) if the copied node 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>′

.

54. The method of claim 32, wherein said index supports sequential operations.

49. 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 a representative keys of said basic partitioned index;

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

50. The method of claim 49, wherein said storage medium being an external memory.

51. The method of claim 50, wherein said storage medium being further an internal memory.

52. The method of claim 49, wherein said storage medium being an internal memory.

53. The method of claim 49, capable of supporting the ODBC standard.

55. The method of claim 49, wherein said index supports sequential operations.

56. The method of claim 49, wherein said constructing step (b) includes:

(a) If B (in I<sub>h−

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.

57. The method according to claim 56, performed on the fly.

58. The method according to claim 56, performed post factum.

59. 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 a representative keys of said trie;

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

60. The method of claim 59, wherein said index supports sequential operations.

61. 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 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.

62. The data processing system according to claim 61, wherein at least some data records that are associated to said leaf nodes are held in at least one separate file.

63. The data processing system according to claim 61, wherein at least one leaf is associated with more than one data record.

64. A method for inserting a new data record into an existing PAIF according to claim 61 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 discrening 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.

65. A method for obtaining a balanced PAIF index;

the PAIF including blocks each accommodating a plurality of nodes and links originated from said nodes;

leaf nodes from among said nodes are associated with data records;

the method comprising executing the following steps as many times as required;

(i) replacing a block, constituting a replaced block, with at least two split blocks such that few from among the nodes of said split block are accommodated within one of said split blocks and the remaining nodes from among the nodes of said split block are accommodated within other split blocks;

(ii) copying at least one node from among the nodes of said replaced block into a block such that said at least two split blocks being children blocks thereof.

66. 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;

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.

67. 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;

the index is arranged in blocks;

such that 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.

68. In a computer system having a storage medium,

a data structure that includes an index over the keys of data records;

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.

69. 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;

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.

70. The storage medium of claim 69, wherein said index constitutes a layered index.

71. The storage medium according to claim 70, wherein said data record of the first type and said subordinated data record of the second type constitute one to one relationship.

72. The storage medium of claim 70, wherein the basic partitioned index of said layered index being a trie.

73. The storage medium according to claim 69 wherein said data record of the first type and said subordinated data record of the second type constitute one to one relationship.

74. The storage medium of claim 69, wherein said index includes a trie.

75. The storage medium of claim 69, wherein for accessing or updating transaction in respect of subordinated data record having composite key K1 . . . Kn, there exists in the index a subordinated search path that leads to the subordinated data record according to the composite key K1 . . . Kn;

the subordinated search path includes a search path to a data record having key K1 . . . kn−

1.

76. 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;

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.

77. The storage medium of claim 76, wherein said designated index constitutes a layered index.

78. The storage medium according to claim 77, wherein said designated index constituting a multi-dimensional index.

79. The storage medium according to claim 78, wherein said designated index constituting a multi-model index.

80. The storage medium according to claim 77, wherein said designated index constituting a multi-model index.

81. The storage medium according to claim 76, wherein said multimodel includes relational model.

82. The storage medium according to claim 76, wherein said multimodel includes object oriented model.

83. The storage medium according to claim 76, wherein said multimodel includes object relational model.

84. The storage medium according to claim 76, wherein said multimodel complies with a client server model.

85. The storage medium according to claim 76, wherein said designated index constituting a multi-dimensional index.

86. The storage medium according to claim 85, wherein said data record of the first type and said subordinated data record of the second type constitute one to many relationship.

87. The storage medium according to claim 76, wherein said designated index constituting a multi-model index.

88. The storage medium according to claim 87, wherein said multi-model includes relational model.

89. The storage medium according to claim 87, wherein said multimodel includes object oriented model.

90. The storage medium according to claim 87, wherein said multimodel includes object relational model.

91. The storage medium according to claim 87, wherein said multimodel complies with a client server model.

92. The storage medium according to claim 76, wherein said data record of the first type and said subordinated data record of the second type constitute one to many relationship.

93. The storage medium of claim 76, wherein said index includes a trie.

94. The storage medium of claim 76, wherein for accessing or updating transaction in respect of subordinated data record having composite key K1 . . . Kn, there exists in the index a subordinated search path that leads to the subordinated data record according to the composite key K1 . . . Kn;

the subordinated search path includes a search path to a data record having key K1 . . . kn−

1.

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

an index being stored in the storage medium and constructed over the keys of said data records that are stored in blocks;

the index being arranged in blocks with the leaf blocks being linked to data records by means of links;

said index is characterized in that at least one of said links is shared by at least two data records stored in the same block.

96. The storage medium of claim 95, wherein said index being constituted by a trie.