Database apparatus

A memory for storing data for access by an application program being executed on a data processing system, comprising:

• at least one probabilistic access indexing file (PAIF) that includes:
• a plurality of nodes each of which, except for the leaf nodes, is connected by means of at least one link to a respective at least one child node;
• each leaf node in said PAIF is associated with at least one data record accessible to said user application program;
• at least a portion of said data record constitutes an n-long-bit search-key having a most-significant-bit (MSB) thereof at an offset 0 and the remaining n−1 bits thereof at respective offsets 1 to n−1;
• selected nodes in said PAIF represent, each, a given offset of an l-bit-long search-key-portion within said n-long-bit search key;
• link(s) originated from each one of said selected nodes represents, each, a unique value of said l-bit-long search key portion;
• for each one of said selected nodes, except for the leaf node, there exists at least one node, subordinated thereto, having an offset larger than the given offset of said one selected node;
• whereby for any search key in a record associated with a leaf node of said PAIF, there is defined a search path that includes a series of units, each consisting of a node from among said selected nodes, and a link;
• the search path commencing at the root node and ending at said leaf node such that for any unit in the series, the value of the l-bit-long search-key-portion at a given offset as indicated, respectively by the link and the node of said unit, conforms the value of the corresponding l-bit-long portion at said given offset within said search key.

A data processing system including a processor device associated with a memory device;

• said processor device is capable of running at least one user application program capable of communicating with a database management system that includes a database file management system, for accessing data records stored in said memory device;
• said database file management system comprising:
• at least one probabilistic 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 a 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-PAIFs being arranged, each, in a block;
• said database file management system is further capable of arranging said blocks as an essentially balanced tree of blocks.

A memory for storing data for access by an application program being executed in a data processing system comprised of:

• at least one probabilistic 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 a 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-PAIFs being arranged, each, in a block;
• said database file management system is further capable of arranging said blocks as an essentially balanced tree of blocks.

A data processing system including a processor device associated with a memory device;

• said processor device is capable of running at least one user application program capable of communicating with a database management system that includes a database file management system, for accessing data records stored in said memory device;
• said database file management system comprising:
• at least one probabilistic 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 a 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 amongst said selected nodes, represent, each, a unique value of said search key portion;
• the PAIF having at least two sub-PAIFs being arranged, each, in a block;
• said PAIF represents ordered structure of said data records.

A method of maintaining a balanced tree structure when a block in the tree is filled with nodes;

• said block constituting a full block;
• the tree including blocks each accommodating a plurality of nodes and links originated from said nodes;
• leaf nodes from among said nodes are connected to data records;
• the method comprising executing the following steps:
• (i) replacing said full 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 the other split block;
• (ii) copying at least one node from among said nodes into a block such that said at least two split blocks being children blocks thereof and the search path characteristics are retained.