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

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.

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.

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.

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.

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.

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.

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.