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.