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

Claim 2

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.

Claim 3

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

Claim 4

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

Claim 5

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

Claim 6

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

Claim 7

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

Claim 8

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

Claim 9

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

Claim 10

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.

Claim 11

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

Claim 12

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

Claim 13

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

Claim 14

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

Claim 15

The layered index I 0 , . . . , I h according to claim 1 , comprising: a representative index I 1 , . . . , I h constructed such that any Ij is constructed over the representative keys of Ij−1.

Claim 16

The layered index I 0 , . . . , I h according to claim 14 , wherein I h is fully contained in one block.

Claim 17

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 h−1 leading to k; (b) repeating step (a) until reaching the block of I 0 that is associated with the data record with key k, if exists.

Claim 18

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 h−1 leading to k; (b) repeating step (a) until reaching the block B of I 0 that is associated with the data record with key k, if exists; (c) associating r to B.

Claim 19

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 h−1 leading to k; (b) repeating step (a) until reaching the block B of I 0 that is associated with the data record with key k, if exists; (c) disconnecting r from B.

Claim 20

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.

Claim 21

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.

Claim 22

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

Claim 23

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

Claim 24

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

Claim 25

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

Claim 26

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 h−1 leading to k; (b) repeating step (a) until reaching the block of I 0 that is associated with the data record with key k, if exists.

Claim 27

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 h−1 leading to k; (b) repeating step (a) until reaching the block B of I 0 that is associated with the data record with key k, if exists; (c) associating r to B.

Claim 28

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 h−1 leading to k; (b) repeating step (a) until reaching the block B of I 0 that is associated with the data record with key k, if exists; (c) disconnecting r from B.

Claim 29

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.

Claim 30

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.

Claim 31

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

Claim 32

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

Claim 33

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

Claim 34

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

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

Claim 36

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.

Claim 37

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

Claim 38

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

Claim 39

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

Claim 40

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

Claim 41

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

Claim 42

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

Claim 43

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

Claim 44

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

Claim 45

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

Claim 46

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

Claim 47

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

Claim 48

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

Claim 49

The method of claim 32 , wherein said construction step (b) includes: (a) If B (in I h−1 ) 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.

Claim 50

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

Claim 51

The method according to claim 45 , performed post factum.

Claim 52

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 i−1 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 i−1 ′ (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 i−1 ′; (e) if the copied node has no direct link, a direct link is added from the copied node to the block B i−1 ; (f) a far link added from the copied node to the block B i−1 ′ 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 i−1 ′.

Claim 53

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.

Claim 54

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.

Claim 55

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

Claim 56

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

Claim 57

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

Claim 58

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

Claim 59

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

Claim 60

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

Claim 61

The method of claim 49 , wherein said constructing step (b) includes: (a) If B (in I h−1 ) 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.

Claim 62

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

Claim 63

The method according to claim 56 , performed post factum.

Claim 64

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.

Claim 65

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.

Claim 66

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

Claim 67

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.

Claim 68

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.

Claim 69

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.

Claim 70

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

Claim 71

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.

Claim 74

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.

Claim 75

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.

Claim 76

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.

Claim 77

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.

Claim 78

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.

Claim 79

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.

Claim 80

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.

Claim 81

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.

Claim 82

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

Claim 83

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.

Claim 84

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

Claim 85

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.

Claim 86

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

Claim 87

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

Claim 88

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.

Claim 89

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.

Claim 90

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

Claim 91

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

Claim 92

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

Claim 93

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

Claim 94

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

Claim 95

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

Claim 96

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

Claim 97

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

Claim 98

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

Claim 99

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.

Claim 100

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

Claim 101

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

Claim 102

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

Claim 103

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

Claim 104

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

Claim 105

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.

Claim 106

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

Claim 107

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

Claim 108

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.

Claim 109

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.

Claim 110

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

Claim 111

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.

Claim 112

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