СПОСОБ И СИСТЕМА РАСПРЕДЕЛЕННОГО ХРАНЕНИЯ ДАННЫХ

1. Способ распределенного хранения данных, включающий:
выделение одного или нескольких деревьев поиска, подлежащих отслеживанию, причем деревья поиска содержат указатели на один или несколько элементов дерева;
выделение одной или нескольких подходящих секций хранения, каждая из которых: соответствует памяти, выделенной на соответствующем устройстве хранения данных, содержит один или несколько элементов деревьев и отмечена как закрытая;
обход деревьев поиска для нахождения элементов деревьев, на которые на текущий момент времени имеются указатели;
указание тех подходящих секций хранения, которые не содержат элементы деревьев, на которые имеются указатели, как секции хранения, содержащие "мусор"; и
для одной или нескольких секций хранения, содержащих "мусор", освобождение соответствующей памяти, выделенной в соответствующем устройстве хранения данных.
2. Способ по 1, включающий также:
сохранение точки восстановления;
приостановку обхода деревьев поиска;
определение первого из элементов дерева поиска, с которого необходимо возобновлять обход, в соответствии с точкой восстановления; и
возобновление обхода деревьев поиска с указанного первого элемента дерева.
3. Способ по п. 2, в котором приостановка обхода деревьев поиска включает приостановку обхода в связи с обновлением дерева поиска.
4. Способ по п. 3, в котором приостановка обхода деревьев поиска включает приостановку обхода в связи с обновлением журнала дерева поиска.
5. Способ по п. 2, в котором сохранение точки восстановления включает сохранение информации о последнем обходимом элементе дерева поиска.
6. Способ по п. 5, в котором сохранение информации о последнем обходимом элементе дерева поиска включает сохранение ключа поиска, связанного с этим элементом.
7. Способ по п. 6, в котором определение первого из элементов дерева поиска, с которого необходимо возобновлять обход, включает определение первого из элементов дерева поиска, с которого необходимо возобновлять обход, в соответствии с ключом поиска, связанным с последним обходимым элементом дерева поиска.
8. Способ по п. 7, в котором определение первого из элементов дерева поиска, с которого необходимо возобновлять обход, включает нахождение элемента дерева поиска, расположенного слева от последнего обходимого элемента дерева поиска.
9. Способ по п. 2, в котором сохранение точки восстановления включает ее сохранение в устройстве хранения данных, совместно используемом первым и вторым узлами кластера хранения, причем приостановка обхода деревьев поиска выполняется первым узлом хранения, а возобновление обхода деревьев поиска выполняется вторым узлом хранения.
10. Способ по п. 9, в котором приостановка обхода деревьев поиска включает выявление изменения принадлежности дерева.
11. Распределенная система хранения данных, содержащая:
множество устройств хранения данных;
два или более узлов хранения данных, каждый из которых содержит модуль деревьев поиска, сконфигурированный для:
выделения одного или нескольких деревьев поиска, подлежащих отслеживанию, причем деревья поиска содержат указатели на один или несколько элементов дерева;
выделения одной или нескольких подходящих секций хранения данных, каждая из которых соответствует памяти, выделенной на соответствующем устройстве хранения данных, содержит один или несколько элементов деревьев и отмечена как закрытая;
обхода деревьев поиска для нахождения элементов деревьев, на которые на текущий момент времени имеются указатели;
указания тех подходящих секций хранения, которые не содержат элементы деревьев, на которые имеются указатели, как секции, содержащие "мусор"; и
для одной или нескольких секций хранения, содержащих "мусор", освобождения соответствующей памяти, выделенной в соответствующем устройстве хранения данных.
12. Распределенная система хранения данных по п. 11, в которой модули деревьев поиска сконфигурированы также для:
сохранения точки восстановления;
приостановки обхода деревьев поиска;
определения первого из элементов дерева поиска, с которого следует возобновлять обход, в соответствии с точкой восстановления; и
возобновления обхода деревьев поиска с указанного первого элемента дерева.
13. Распределенная система хранения данных по п. 12, в которой модули деревьев поиска сконфигурированы для приостановки обхода деревьев поиска в связи с обновлением дерева поиска.
14. Распределенная система хранения данных по п. 13, в которой модули деревьев поиска сконфигурированы для приостановки обхода деревьев поиска в связи с обновлением журнала дерева поиска.
15. Распределенная система хранения данных по п. 12, в которой точка восстановления содержит информацию о последнем обходимом элементе дерева поиска.
16. Распределенная система хранения данных по п. 15, в которой точка восстановления содержит ключ поиска, связанный с последним обходимым элементом дерева поиска.
17. Распределенная система хранения данных по п. 16, в которой модули деревьев поиска сконфигурированы для определения первого из элементов дерева поиска, с которого необходимо возобновлять обход, в соответствии с ключом поиска, связанным с последним обходимым элементом дерева поиска.
18. Распределенная система хранения данных по п. 17, в которой модули деревьев поиска сконфигурированы для определения первого из элементов дерева поиска, с которого необходимо возобновлять обход, путем нахождения элемента дерева поиска, расположенного слева от последнего обходимого элемента дерева поиска.
19. Распределенная система хранения данных по п. 12, в которой точка восстановления используется совместно узлами хранения данных и обход деревьев поиска может быть приостановлен на первом узле хранения данных и возобновлен на втором узле хранения данных.
20. Распределенная система хранения данных по п. 19, в которой модули деревьев поиска сконфигурированы для приостановки обхода деревьев поиска в связи с изменением принадлежности дерева поиска.