Lockless concurrent B-tree index meta access method for cached nodes

• US 5,283,894 A
• Filed: 01/30/1991
• Issued: 02/01/1994
• Est. Priority Date: 04/11/1986
• Status: Expired due to Term

• Current Assignee: Roger L. Deran
• Original Assignee: Roger L. Deran
• Inventors: Deran, Roger L.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): DONAGHUE, LARRY D
• Application Number:
  US07/648,142
• Time in Patent Office: 1,098 Days
• Field of Search: 395/600, 364/DIG. 1, 364/DIG. 2
• US Class Current: 707/704
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A user interface for a database management system uses an interactive display to display information selected from the database in magnitude ordered rows comprising a set of items. Each row is an assertion consisting of a plurality of components including an entity, an attribute and a value of the attribute. The components are arranged in that fixed order in decreasing significance, respectively. In the database management system, the database is itself also stored in this format. A database engine in the database management system utilizes a B-tree index to the database and a meta accessing method for items from the database in a working cache.

Claims

1. A data storage and retrieval system comprising:

first generating means for generating a key sequence for constructing a basic index tree structure;

second generating means for generating said basic tree index structure responsive to said key sequence;

secondary direct access storage means, coupled to said first and second generating means, for storing a plurality of nodes of said basic tree index structure and corresponding key-indexed data;

primary direct-access memory means for storing a selected subset of said plurality of nodes of said basic tree index structure and said corresponding key indexed data;

means, coupled between said secondary storage means and said primary memory means, for copying said selected subset from said secondary storage means to said primary memory means;

means, coupled to said primary memory means, for modifying said selected subset;

first accessing means, coupled to said secondary storage means, responsive to a first external inputted key access sequence for sequential accessing said basic tree index structure and said corresponding key indexed data and to an external inputted key value for randomly accessing said basic tree index structure and corresponding key indexed data;

second accessing means, coupled to said primary memory means, responsive to a second external inputted key access sequence for sequentially accessing said selected subset and external inputted key value for randomly accessing said selected subset;

third accessing means, coupled to said primary memory means, for accessing said copied or modified selected subset;

said third accessing means includes determining means for determining a key value range of one of said plurality of nodes of said selected subset and means responsive to an external inputted key value within said key value range to access said selected subset and corresponding key indexed data.

2. The data storage and retrieval of claim 1, wherein the second accessing means and the third accessing means are configured according to a meta access method;

said primary direct access memory means configured to store and retrieve data in a fixed length; and

,

said secondary direct access storage means configured to store said plurality of nodes in said in said fixed length units, wherein branches of said basic tree index structure are the addresses of said fixed length units.

3. The data storage and retrieval system of claim 2, in which said meta access method is a tree.

4. The data storage and retrieval system of claim 3, in which said tree is a B-tree.

5. The data storage and retrieval system of claim 4, in which said basic tree indexed structure is a B-tree.

6. The data storage and retrieval system of claim 4, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.

7. The data storage and retrieval system of claim 4, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.

8. The data storage and retrieval system of claim 5, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.

9. The data storage and retrieval system of claim 5, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.

10. The data storage and retrieval system of claim 6, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.

11. The data storage and retrieval system of claim 8, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.

12. The data storage and retrieval system of claim 2, in which said basic tree indexed structure is a B-tree.

13. The data storage and retrieval system of claim 12, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.

14. The data storage and retrieval system of claim 12, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.

15. The data storage and retrieval system of claim 13, in which a data format of fixed length units of basic tree indexed structure allows prefix compression of keys.

16. The data storage and retrieval system of claim 3, in which said basic tree indexed structure is a B-tree.

17. The data storage and retrieval system of claim 16, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.

18. The data storage and retrieval system of claim 16, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.

19. The data storage and retrieval system of claim 18, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.

20. The data storage and retrieval system of claim 2, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.

21. The data storage and retrieval system of claim 20, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.

22. The data storage and retrieval system of claim 3, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.

23. The data storage and retrieval system of claim 22, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.

24. The data storage and retrieval system of claim 2, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.

25. The data storage and retrieval system of claim 3, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.