Method and System for Managing An Index Arrangement for a Directory

• US 20070078888A1
• Filed: 09/28/2006
• Published: 04/05/2007
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Harvey, Richard, Ramsay, Ronald
• Granted Patent: US 7,822,736 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

According to one embodiment of the invention, a method for managing an index arrangement for a directory includes storing a plurality of data values from the directory in an alternate evaluator. The alternate evaluator includes a processor operable to process a directory operation. The method also includes generating a first index corresponding to the plurality of data values, the first index comprising at least one page having a variable size. The method further includes storing a first value in the at least one page and a corresponding pointer to each occurrence of the respective data value stored in the alternate evaluator.

Claims

1. A method for managing an index arrangement for a directory, comprising:

storing, in an alternate evaluator, a plurality of data values from the directory, the alternate evaluator comprising a processor operable to process a directory operation;

generating, by the alternate evaluator, a first index corresponding to the plurality of data values, the first index comprising at least one page having a variable size; and

storing, in the alternate evaluator, a first value in the at least one page and a corresponding pointer to each occurrence of the respective data value stored in the alternate evaluator.

2. The method of claim 1, wherein the first value in the at least one page comprises a syntax normalized value.

3. The method of claim 1, further comprising:

storing, in the alternate evaluator, a counter in the at least one page, wherein the counter is indicative of a total number of pointers in the page; and

resizing, by the alternate evaluator, the page based on the counter.

4. The method of claim 1, further comprising generating, by the alternate evaluator, a second index, the second index comprising at least one page, the at least one page comprising one or more pointers from the second index to the first index.

5. The method of claim 4, further comprising adding, by the alternate evaluator, a second level to the second index.

6. The method of claim 4, further comprising balancing, by the alternate evaluator, the second index to increase the occupancy ratio of the second index by organizing the second index to provide a particular number of pointers at each page.

7. The method of claim 4, further comprising sorting, by the alternate evaluator, the second index to support a binary search algorithm.

8. The method of claim 4, further comprising storing, in the alternate evaluator, the second index as a B-tree.

9. A system for managing an index arrangement for a directory, comprising:

an alternate evaluator operable to process a directory operation, the alternate evaluator comprising;

a processor; and

a storage device embodying a program of instructions operable, when executed on the processor, to;

store a plurality of data values from the directory;

generate a first index corresponding to the plurality of data values, the first index comprising at least one page having a variable size; and

store a first value in the at least one page and a corresponding pointer to each occurrence of the respective data value stored in the alternate evaluator.

10. The system of claim 9, wherein the first value in the at least one page comprises a syntax normalized value.

11. The system of claim 9, wherein the program of instructions is further operable to:

store a counter in the at least one page, wherein the counter is indicative of a total number of pointers in the page; and

resize the page based on the counter.

12. The system of claim 9, wherein the program of instructions is further operable to generate a second index, the second index comprising at least one page, the at least one page comprising one or more pointers from the second index to the first index.

13. The system of claim 12, wherein the program of instructions is further operable to add a second level to the second index.

14. The system of claim 12, wherein the program of instructions is further operable to balance the second index to increase the occupancy ratio of the second index by organizing the second index to provide a particular number of pointers at each page.

15. The system of claim 12, wherein the program of instructions is further operable to sort the second index to support a binary search algorithm.

16. The system of claim 12, wherein the program of instructions is further operable to store the second index as a B-tree.

17. Logic encoded in media, the logic being operable, when executed on a processor, to:

store a plurality of data values from the directory;

generate a first index corresponding to the plurality of data values, the first index comprising at least one page having a variable size; and

store a first value in the at least one page and a corresponding pointer to each occurrence of the respective data value stored in the alternate evaluator.

18. The logic of claim 17, wherein the first value in the at least one page comprises a syntax normalized value.

19. The logic of claim 17, wherein the logic is further operable to:

store a counter in the at least one page, wherein the counter is indicative of a total number of pointers in the page; and

resize the page based on the counter.

20. The logic of claim 17, wherein the logic is further operable to generate a second index, the second index comprising at least one page, the at least one page comprising one or more pointers from the second index to the first index.

21. The logic of claim 20, wherein the logic is further operable to add a second level to the second index.

22. The logic of claim 20, wherein the logic is further operable to balance the second index to increase the occupancy ratio of the second index by organizing the second index to provide a particular number of pointers at each page.

23. The logic of claim 20, wherein the logic is further operable to sort the second index to support a binary search algorithm.

24. The logic of claim 20, wherein the logic is further operable to store the second index as a B-tree.