Method, system, program, and computer readable medium for indexing object oriented objects in an object oriented database

• US 20020161781A1
• Filed: 04/27/2001
• Published: 10/31/2002
• Est. Priority Date: 04/27/2001
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Taylor, Julian S., Leong, Terence
• Granted Patent: US 6,772,172 B2
• Time in Patent Office: Days
• US Class Current: 707/103R
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

Provided is a method, system, program, and data structures for indexing object oriented objects in an object oriented database. an object data structure is provided including a plurality of object oriented objects, wherein each object includes a key value, and wherein each object is associated with an object index. A node data structure is provided including nodes, wherein each node represents one object in the object store and includes one object index used to access the object represented by the node in the object store. The nodes in the node data structure are organized according to the key values in the objects represented by the nodes. The node data structure is used to access the objects in the object store.

Claims

1. A method for indexing object oriented objects in an object oriented database, comprising:

providing an object data structure including a plurality of object oriented objects, wherein each object includes a key value, and wherein each object is associated with an object index;

providing a node data structure including nodes, wherein each node represents one object in the object store and includes one object index used to access the object represented by the node in the object store, and wherein the nodes in the node data structure are organized according to the key values in the objects represented by the nodes; and

using the node data structure to access the objects in the object store.

2. The method of claim 1, wherein each node is associated with one node index used to access the node in the node data structure, wherein each node is further capable of including one or more node indexes to further nodes, further comprising:

receiving a search key;

accessing one node using the node index for the node;

using the object index in the accessed node to access the object in the object store;

accessing the key value in the accessed object; and

performing an operation if the accessed key value matches the search key.

3. The method of claim 2, further comprising:

if the accessed key value does not match the search key and if the accessed node includes a node index to another node, then using the node index to access the further node and performing another iteration of the steps of using the object index in the further node to access one object in the object store, accessing the key value in the accessed object, and performing the operation if the accessed key value matches the search key.

4. The method of claim 2, wherein the nodes represent nodes in a tree data structure, wherein the further node accessed using the node index in one node comprises a child node of the node including the node index.

5. The method of claim 2, wherein each node is associated with a first node index and a second node index, wherein using the first and second node indexes to access the further node comprises:

using the first node index to access the further node if the search key is less than the accessed key value; and

using the second node index to access the further node if the search key is greater than the accessed key value.

6. The method of claim 2, wherein a node that does not include a value indexing another node in one node index comprises a leaf node, wherein the operation performed comprises a request to add a received object to the object data structure, further comprising:

if the accessed key value does not match the search key and if the accessed node comprises a leaf node, then performing;

(i) adding the received object to the object data structure;

(ii) associating one object index with the received object;

(iii) generating a new node for the received object including the object index associated with the received object;

(iv) generating one new node index to associate with the received object that is used to access the new node in the node data structure; and

(iv) updating the leaf node to include the new node index to the new node.

7. The method of claim 6, wherein the leaf node includes a first node index and a second node index, wherein updating the leaf node to include the new node index further comprises:

updating the first node index to include the new node index if the search key is less than the accessed key value; and

updating the second node index to include the new node index if the search key is greater than the accessed key value.

8. The method of claim 2, wherein accessing the key value in the accessed object comprises:

issuing a request to access one field in the accessed object including the key value.

9. The method of claim 8, wherein the field including the key value is embedded within one object embedded within the accessed object, wherein issuing the request comprises issuing the request against the accessed object, wherein the accessed object issues the request against the embedded object for the field including the key value.

10. The method of claim 2, wherein the operation comprises a request for one object in the object data structure having the key value matching the search key, and wherein performing the operation comprises:

returning the accessed object if the key value in the accessed object matches the search key.

11. The method of claim 2, wherein one node in the node data structure comprises a root node, wherein a root node index used to access the root node in the node data structure is maintained in an additional data structure, wherein the first node accessed comprises the root node, and further comprising accessing the root node index from the additional data structure when accessing a first node in the node data structure.

12. The method of claim 1, wherein the object data structure and node data structure comprise an array data structure, and wherein the object and node indexes are used to access the associated object and node, respectively, in the array.

13. The method of claim 12, wherein the array data structure comprises a one dimensional array that can expand or contract automatically to accommodate adding and removing elements therefrom.

14. The method of claim 13, wherein the array data structure comprises a Java vector.

15. The method of claim 1, wherein the objects in the object data structure are instantiated from the same class and include the same field having the key value.

16. The method of claim 1, wherein each object includes multiple key value fields used to organize the nodes in the node data structure.

17. The method of claim 1, wherein the objects in the object data structure are instantiated from different classes.

18. The method of claim 1, wherein the operation is a member of a set of database operations comprising adding a new object, searching for one object, updating one object, and deleting one object in the object data store.

19. The method of claim 1, wherein there are multiple object data structures, wherein there is one node data structure for each object data structure, and wherein each object data structure includes objects instantiated from a same class, and wherein the classes used to instantiate the objects in different object data structures comprise different classes.

20. A system for indexing object oriented objects in an object oriented database, comprising:

means for providing an object data structure including a plurality of object oriented objects, wherein each object includes a key value, and wherein each object is associated with an object index;

means for providing a node data structure including nodes, wherein each node represents one object in the object store and includes one object index used to access the object represented by the node in the object store, and wherein the nodes in the node data structure are organized according to the key values in the objects represented by the nodes; and

means for using the node data structure to access the objects in the object store.

21. The system of claim 20, wherein each node is associated with one node index used to access the node in the node data structure, wherein each node is further capable of including one or more node indexes to further nodes, further comprising:

means for receiving a search key;

means for accessing one node using the node index for the node;

means for using the object index in the accessed node to access the object in the object store;

means for accessing the key value in the accessed object; and

means for performing an operation if the accessed key value matches the search key.

22. The system of claim 21, further comprising:

means for using, if the accessed key value does not match the search key and if the accessed node includes a node index to another node, the node index to access the further node and performing another iteration of the steps of using the object index in the further node to access one object in the object store, accessing the key value in the accessed object, and performing the operation if the accessed key value matches the search key.

23. The system of claim 21, wherein the nodes represent nodes in a tree data structure, wherein the further node accessed using the node index in one node comprises a child node of the node including the node index.

24. The system of claim 21, wherein each node is associated with a first node index and a second node index, wherein the means for using the first and second node indexes to access the further node performs:

using the first node index to access the further node if the search key is less than the accessed key value; and

using the second node index to access the further node if the search key is greater than the accessed key value.

25. The system of claim 21, wherein a node that does not include a value indexing another node in one node index comprises a leaf node, wherein the operation performed comprises a request to add a received object to the object data structure;

means for performing, if the accessed key value does not match the search key and if the accessed node comprises a leaf node;

(i) adding the received object to the object data structure;

(ii) associating one object index with the received object;

(iii) generating a new node for the received object including the object index associated with the received object;

(iv) generating one new node index to associate with the received object that is used to access the new node in the node data structure; and

(iv) updating the leaf node to include the new node index to the new node.

26. The system of claim 25, wherein the leaf node includes a first node index and a second node index, wherein the means for updating the leaf node to include the new node index further performs:

updating the first node index to include the new node index if the search key is less than the accessed key value; and

updating the second node index to include the new node index if the search key is greater than the accessed key value.

27. The system of claim 21, wherein the means for accessing the key value in the accessed object further performs:

issuing a request to access one field in the accessed object including the key value.

28. The system of claim 27, wherein the field including the key value is embedded within one object embedded within the accessed object, wherein the means for issuing the request issues the request against the accessed object, wherein the accessed object issues the request against the embedded object for the field including the key value.

29. The system of claim 21, wherein the operation comprises a request for one object in the object data structure having the key value matching the search key, and wherein the means for performing the operation performs:

returning the accessed object if the key value in the accessed object matches the search key.

30. The system of claim 21, wherein one node in the node data structure comprises a root node, wherein a root node index used to access the root node in the node data structure is maintained in an additional data structure, wherein the first node accessed comprises the root node, and further comprising accessing the root node index from the additional data structure when accessing a first node in the node data structure.

31. The system of claim 20, wherein the object data structure and node data structure comprise an array data structure, and wherein the object and node indexes are used to access the associated object and node, respectively, in the array.

32. The system of claim 21, wherein the array data structure comprises a one dimensional array that can expand or contract automatically to accommodate adding and removing elements therefrom.

33. The system of claim 21, wherein the array data structure comprises a Java vector.

34. The system of claim 20, wherein the objects in the object data structure are instantiated from the same class and include the same field having the key value.

35. The system of claim 20, wherein each object includes multiple key value fields used to organize the nodes in the node data structure.

36. The system of claim 20, wherein the objects in the object data structure are instantiated from different classes.

37. The system of claim 20, wherein the operation is a member of a set of database operations comprising adding a new object, searching for one object, updating one object, and deleting one object in the object data store.

38. The system of claim 20, wherein there are multiple object data structures, wherein there is one node data structure for each object data structure, and wherein each object data structure includes objects instantiated from a same class, and wherein the classes used to instantiate the objects in different object data structures comprise different classes.

40. The article of manufacture of claim 39, wherein each node is associated with one node index used to access the node in the node data structure, wherein each node is further capable of including one or more node indexes to further nodes, further comprising:

receiving a search key;

accessing one node using the node index for the node;

using the object index in the accessed node to access the object in the object store;

accessing the key value in the accessed object; and

performing an operation if the accessed key value matches the search key.

41. The article of manufacture of claim 40, further comprising:

if the accessed key value does not match the search key and if the accessed node includes a node index to another node, then using the node index to access the further node and performing another iteration of the steps of using the object index in the further node to access one object in the object store, accessing the key value in the accessed object, and performing the operation if the accessed key value matches the search key.

42. The article of manufacture of claim 40, wherein the nodes represent nodes in a tree data structure, wherein the further node accessed using the node index in one node comprises a child node of the node including the node index.

43. The article of manufacture of claim 40, wherein each node is associated with a first node index and a second node index, wherein using the first and second node indexes to access the further node comprises:

using the first node index to access the further node if the search key is less than the accessed key value; and

using the second node index to access the further node if the search key is greater than the accessed key value.

44. The article of manufacture of claim 40, wherein a node that does not include a value indexing another node in one node index comprises a leaf node, wherein the operation performed comprises a request to add a received object to the object data structure, further comprising:

if the accessed key value does not match the search key and if the accessed node comprises a leaf node, then performing;

(i) adding the received object to the object data structure;

(ii) associating one object index with the received object;

(iii) generating a new node for the received object including the object index associated with the received object;

(iv) generating one new node index to associate with the received object that is used to access the new node in the node data structure; and

(iv) updating the leaf node to include the new node index to the new node.

45. The article of manufacture of claim 40, wherein the leaf node includes a first node index and a second node index, wherein updating the leaf node to include the new node index further comprises:

updating the first node index to include the new node index if the search key is less than the accessed key value; and

updating the second node index to include the new node index if the search key is greater than the accessed key value.

46. The article of manufacture of claim 40, wherein accessing the key value in the accessed object comprises:

issuing a request to access one field in the accessed object including the key value.

47. The article of manufacture of claim 46, wherein the field including the key value is embedded within one object embedded within the accessed object, wherein issuing the request comprises issuing the request against the accessed object, wherein the accessed object issues the request against the embedded object for the field including the key value.

48. The article of manufacture of claim 40, wherein the operation comprises a request for one object in the object data structure having the key value matching the search key, and wherein performing the operation comprises:

returning the accessed object if the key value in the accessed object matches the search key.

49. The article of manufacture of claim 40, wherein one node in the node data structure comprises a root node, wherein a root node index used to access the root node in the node data structure is maintained in an additional data structure, wherein the first node accessed comprises the root node, and further comprising accessing the root node index from the additional data structure when accessing a first node in the node data structure.

50. The article of manufacture of claim 39, wherein the object data structure and node data structure comprise an array data structure, and wherein the object and node indexes are used to access the associated object and node, respectively, in the array.

51. The article of manufacture of claim 50, wherein the array data structure comprises a one dimensional array that can expand or contract automatically to accommodate adding and removing elements therefrom.

52. The article of manufacture of claim 51, wherein the array data structure comprises a Java vector.

53. The article of manufacture of claim 39, wherein the objects in the object data structure are instantiated from the same class and include the same field having the key value.

54. The article of manufacture of claim 39, wherein each object includes multiple key value fields used to organize the nodes in the node data structure.

55. The article of manufacture of claim 39, wherein the objects in the object data structure are instantiated from different classes.

56. The article of manufacture of claim 39, wherein the operation is a member of a set of database operations comprising adding a new object, searching for one object, updating one object, and deleting one object in the object data store.

57. The article of manufacture of claim 39, wherein there are multiple object data structures, wherein there is one node data structure for each object data structure, and wherein each object data structure includes objects instantiated from a same class, and wherein the classes used to instantiate the objects in different object data structures comprise different classes.

59. The computer readable medium of claim 58, wherein each node is associated with one node index used to access the node in the node data structure, wherein each node is further capable of including one or more node indexes to further nodes, wherein the node index for one node is used to access the node, wherein the object index in the accessed node is used to access the object in the object store, wherein the key value is accessed from the accessed object, and wherein an operation is performed if the accessed key value matches the search key.

60. The computer readable medium of claim 59, wherein if the accessed key value does not match the search key and if the accessed node includes a node index to another node, then the node index is used to access the further node and another iteration is performed of the steps of using the object index in the further node to access one object in the object store, accessing the key value in the accessed object, and performing the operation if the accessed key value matches the search key.

61. The computer readable medium of claim 59, wherein the nodes represent nodes in a tree data structure, wherein the further node accessed using the node index in one node comprises a child node of the node including the node index.

62. The computer readable medium of claim 59, wherein each node is associated with a first node index and a second node index, wherein the first and second node indexes are used to access the further node by using the first node index to access the further node if the search key is less than the accessed key value and using the second node index to access the further node if the search key is greater than the accessed key value.

63. The computer readable medium of claim 58, wherein the field including the key value is embedded within one object embedded within the accessed object, wherein accessing the key value in the accessed object comprises issuing a request against the accessed object, wherein the accessed object issues a request against the embedded object for the field including the key value.

64. The computer readable medium of claim 59, wherein the operation performed comprises a request for one object in the object data structure having the key value matching the search key, and wherein performing the operation comprises:

returning the accessed object if the key value in the accessed object matches the search key.

65. The computer readable medium of claim 59, further comprising:

a root node data structure including a root node index used to access a root node in the node data structure, and wherein the root node index is accessed from the additional data structure when accessing a first node in the node data structure.

66. The computer readable medium of claim 59, wherein the object data structure and node data structure comprise an array data structure, and wherein the object and node indexes are used to access the associated object and node, respectively, in the array.

67. The computer readable medium of claim 66, wherein the array data structure comprises a one dimensional array that can expand or contract automatically to accommodate adding and removing elements therefrom.

68. The computer readable medium of claim 67, wherein the array data structure comprises a Java vector.

69. The computer readable medium of claim 59, wherein the objects in the object data structure are instantiated from the same class and include the same field having the key value.

70. The computer readable medium of claim 59, wherein each object includes multiple key value fields used to organize the nodes in the node data structure.

71. The computer readable medium of claim 59, wherein the objects in the object data structure are instantiated from different classes.

72. The computer readable medium of claim 59, wherein the operation is a member of a set of database operations comprising adding a new object, searching for one object, updating one object, and deleting one object in the object data store.

73. The computer readable medium of claim 59, wherein there are multiple object data structures, wherein there is one node data structure for each object data structure, and wherein each object data structure includes objects instantiated from a same class, and wherein the classes used to instantiate the objects in different object data structures comprise different classes.

39. An article of manufacture for indexing object oriented objects in an object oriented database by:

providing an object data structure including a plurality of object oriented objects, wherein each object includes a key value, and wherein each object is associated with an object index;

providing a node data structure including nodes, wherein each node represents one object in the object store and includes one object index used to access the object represented by the node in the object store, and wherein the nodes in the node data structure are organized according to the key values in the objects represented by the nodes; and

using the node data structure to access the objects in the object store.

58. A computer readable medium including data structures for indexing object oriented objects in an object oriented database, comprising:

an object data structure including a plurality of object oriented objects, wherein each object includes a key value, and wherein each object is associated with an object index; and

a node data structure including nodes, wherein each node represents one object in the object store and includes one object index used to access the object represented by the node in the object store, and wherein the nodes in the node data structure are organized according to the key values in the objects represented by the nodes, wherein the node data structure is used to access the objects in the object store.