Method and system for indexing in datastores

1. A computer assisted method for indexing information stored in a data-store as a segment tree, the method including:

receiving a new index request for the segment tree driven by at least one of a create operation, a read operation, an update operation, and a delete operation;

creating an index in response to the new index request, the index comprising at least one segment, a first flag, and a last flag, wherein each segment comprises index summary information, wherein the index summary information comprises at least one selected from a group consisting of a covered key range within the segment, a start key within a next segment, and key summary filters; and

storing the index in memory;

organizing an index file, wherein organizing includes at least one of splitting a segment and merging a segment;

covering a key space by indicating at least a first key and a next segment key in each segment and summary segment;

indicating a deleted first key within a segment and a summary segment;

maintaining a covered key space during organization operations; and

streaming index changes to an index file in an append-only manner.

2. The method of claim 1 , wherein creating the index comprises: scanning a segmented index file by segment to identify each of a plurality of keys and their corresponding range; and

creating a summary index based on the identified keys and their corresponding range.

3. The method of claim 2 , further comprising:

determining that the summary index is complete when contiguous segments have been identified that cover an entire key space of the index.

4. The method of claim 2 , wherein segments identify segments they modify through segment back referencing.

5. The method of claim 2 , wherein summary segments identify each of a plurality of first keys and their corresponding segments.

6. The method of claim 1 , wherein each segment comprises at least one selected from a group consisting of index summary information, key elements, key pointers, and value pointers.

7. The method of claim 1 , wherein the index summary information comprises a key summary filter, and wherein the key summary filter is a bloom filter.

8. The method of claim 1 , wherein each segment comprises range covering indexes.

9. The method of claim 1 , further comprising:

incrementally regenerating an in-memory index from a plurality of segments.

10. The method of claim 9 , wherein each segment comprises range covering indexes, the method further comprising:

incrementally regenerating an in-memory index using the range covering indexes.

11. The method of claim 1 , wherein the information is organized in an append-only manner.

12. The method of claim 11 , wherein the index files comprise at least one of unordered keys and ordered keys, the index files being append-only index files.

13. The method of claim 12 , further comprising:

incrementally regenerating an in-memory index from ordered keys using key sampling.

14. The method of claim 13 , wherein each segment comprises a segment size boundary, and wherein the key sampling is performed at the segment size boundaries.

15. The method of claim 14 , wherein key sampling comprises searching for key transitions in order to identify duplicate keys.

16. The method of claim 1 , wherein a segment is split based on a split threshold.

17. The method of claim 16 , wherein the split threshold is determined based on at least one of policy and dynamic optimization criteria.

18. The method of claim 1 , wherein a segment is merged based on a merge threshold.

19. The method of claim 18 , wherein the segment merge threshold is determined based on at least one of policy and dynamic optimization criteria.

20. The method of claim 1 , wherein the index is distributed.

21. The method of claim 20 , wherein the distributed index is subdivided among nodes based on key ranges.

22. The method of claim 21 , wherein multiple nodes comprise the same key range.

23. The method of claim 1 , further comprising:

creating multiple indexes each having a different order;

creating multiple indexes each having different covering key sets; and creating multiple indexed caches of keys and values based on access patterns.

24. The method of claim 1 , further comprising: organizing LRT and VRT files based on index order; and creating non-authoritative index ordered LRT and VRT files.

25. An automated system for indexing information stored in a data-store as a segment tree, the system comprising:

means for receiving a new index request for the segment tree driven by at least one of a create operation, a read operation, an update operation, and a delete operation;

means for creating an index in response to the new index request, the index comprising at least one segment, a first flag, and a last flag, wherein each segment comprises index summary information, wherein the index summary information comprises at least one selected from a group consisting of a covered key range within the segment, a start key within a next segment, and key summary filters; and

means for storing the index in memory;

means for organizing an index file, wherein organizing includes at least one of splitting a segment and merging a segment;

means for covering a key space by indicating at least a first key and a next segment key in each segment and summary segment;

means for indicating a deleted first key within a segment and a summary segment;

means for maintaining a covered key space during organization operations; and

means for streaming index changes to an index file in an append-only manner.

26. A computer program product comprising a non-transitory computer readable medium having control logic stored therein for causing a computer to perform indexing information stored in a data-store as a segment tree, the control logic code for:

receiving a new index request for the segment tree driven by at least one of a create operation, a read operation, an update operation, and a delete operation;

creating an index in response to the new index request, the index comprising at least one segment, a first flag, and a last flag, wherein each segment comprises index summary information, wherein the index summary information comprises at least one selected from a group consisting of a covered key range within the segment, a start key within a next segment, and key summary filters; and

storing the index in memory;

organizing an index file, wherein organizing includes at least one of splitting a segment and merging a segment;

covering a key space by indicating at least a first key and a next segment key in each segment and summary segment;

indicating a deleted first key within a segment and a summary segment;

maintaining a covered key space during organization operations; and

streaming index changes to an index file in an append-only manner.

27. An automated system for indexing information stored in a data-store as a segment tree, the system comprising:

at least one processor;

a user interface functioning via the at least one processor; and

a repository accessible by the at least one processor; wherein the at least one processor is configured to:

receive a new index request for the segment tree driven by at least one of a create operation, a read operation, an update operation, and a delete operation;

create an index in response to the new index request, the index comprising at least one segment, a first flag, and a last flag, wherein each segment comprises index summary information, wherein the index summary information comprises at least one selected from a group consisting of a covered key range within the segment, a start key within a next segment, and key summary filters; and

store the index in memory;

organizing an index file, wherein organizing includes at least one of splitting a segment and merging a segment;

covering a key space by indicating at least a first key and a next segment key in each segment and summary segment;

indicating a deleted first key within a segment and a summary segment;

maintaining a covered key space during organization operations; and

streaming index changes to an index file in an append-only manner.