Одновременное использование документа несколькими потоками

Одновременное использование документа несколькими потоками

Иллюстрации

Показать все

Реферат

УРОВЕНЬ ТЕХНИКИ

[0001] Электронные документы в сегодняшней рабочей обстановке повсеместны. Например, миллионы людей каждый день используют и формируют документы текстового процессора, документы электронной таблицы и другие виды документов. При увеличивающейся важности электронных документов люди предполагают, что программные приложения предоставят еще более мощные инструменты для обращения с электронными документами. Например, люди предполагают, что приложения для обработки текстов предоставят инструменты безошибочной проверки грамматики и орфографии.

[0002] Однако такие инструменты часто требуют больших объемов вычислений. Поскольку такие инструменты требуют больших объемов вычислений, использование таких инструментов может привести к задержкам, которые заметны пользователям. Такие задержки могут вызывать неудовлетворенность пользователя, и поэтому их следует минимизировать.

[0003] Производительность компьютеров в последние годы увеличилась. Однако значительная часть того увеличения обусловлена тем, что отдельные компьютеры теперь могут использовать несколько блоков обработки. Например, более старые компьютеры имели только один блок обработки и поэтому могли выполнять только одну программу единовременно. Новые компьютеры могут иметь несколько блоков обработки и поэтому могут выполнять одновременно несколько программ.

[0004] В некоторых обстоятельствах несколько программ, выполняющихся на нескольких блоках обработки, должны взаимодействовать с одними и теми же данными в электронном документе. Например, если первая программа должна была писать в некоторые данные в электронном документе, тогда как вторая программа пыталась считать те данные, то вторая программа могла считать искаженные данные. Типичным решением этой проблемы для программ является блокировка данных в электронном документе до того, как программы считают данные. Когда программа блокирует данные, никакая другая программа не может писать в те данные. Поэтому, если другой поток хочет писать в данные, пока данные заблокированы, другой поток вынужден ожидать, пока данные не разблокируют. Вынуждение другого потока ждать может привести к задержкам, которые заметны пользователям.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

[0005] Вычислительная система одновременно выполняет поток-конструктор и по меньшей мере один поток-считыватель. Поток-конструктор изменяет документ путем изменения активного представления документа. Поток-считыватель выполняет операции в отношении документа, используя неактивное представление документа. Активное представление документа и неактивное представление документа сохраняются в запоминающем устройстве вычислительной системы. Активное представление документа и неактивное представление документа не включают в себя разные копии одних и тех же данных в запоминающем устройстве. При считывании данных в любом неактивном представлении документа логическая связность обеспечивается без блокирования каких-либо данных в любом неактивном представлении документа.

[0006] Данная сущность изобретения предоставляется для знакомства с набором идей. Эти идеи дополнительно описываются ниже в Подробном описании. Данная сущность изобретения не предназначена для определения ключевых признаков или существенных признаков заявленного предмета изобретения, и также данная сущность не предназначена в качестве содействия при определении объема заявленного предмета изобретения.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0007] Фиг. 1 - блок-схема, иллюстрирующая примерную вычислительную систему.

[0008] Фиг. 2 иллюстрирует примерное дерево документа и массив элементов, который представляет дерево документа.

[0009] Фиг. 3 иллюстрирует примерное представление документа.

[0010] Фиг. 4 иллюстрирует примерное представление документа, когда вставляются элементы.

[0011] Фиг. 5 иллюстрирует примерное представление документа, когда удаляются элементы.

[0012] Фиг. 6 иллюстрирует примерное представление документа, когда дополнительные элементы вставляются в существующий фрагмент.

[0013] Фиг. 7 иллюстрирует примерное дерево индексов.

[0014] Фиг. 8 иллюстрирует примерное дерево индексов с наложенными узлами замены, принадлежащими поздней версии дерева индексов.

[0015] Фиг. 9 - блок-схема алгоритма, иллюстрирующая примерную операцию, выполненную приложением, когда приложение запускается.

[0016] Фиг. 10 - блок-схема алгоритма, иллюстрирующая примерную операцию вставки элемента.

[0017] Фиг. 11 - блок-схема алгоритма, иллюстрирующая продолжение примерной операции вставки элемента.

[0018] Фиг. 12 - блок-схема алгоритма, иллюстрирующая дальнейшее продолжение примерной операции вставки элемента.

[0019] Фиг. 13 - блок-схема алгоритма, иллюстрирующая дальнейшее продолжение примерной операции вставки элемента.

[0020] Фиг. 14 - блок-схема алгоритма, иллюстрирующая примерную операцию удаления элемента.

[0021] Фиг. 15 - блок-схема алгоритма, иллюстрирующая продолжение примерной операции удаления элемента.

[0022] Фиг. 16 - блок-схема алгоритма, иллюстрирующая продолжение примерной операции удаления элемента.

[0023] Фиг. 17 - блок-схема алгоритма, иллюстрирующая продолжение примерной операции удаления элемента.

[0024] Фиг. 18 - блок-схема алгоритма, иллюстрирующая примерную операцию потока-считывателя.

[0025] Фиг. 19 - блок-схема алгоритма, иллюстрирующая примерную операцию потока-считывателя.

[0026] Фиг. 20 - блок-схема, иллюстрирующая примерное вычислительное устройство.

ПОДРОБНОЕ ОПИСАНИЕ

[0027] Фиг. 1 - блок-схема, иллюстрирующая примерную вычислительную систему 100. Как проиллюстрировано в примере из фиг. 1, пользователь 102 использует вычислительную систему 100 для доступа к приложению 104. Приложение 104 позволяет пользователю 102 взаимодействовать с документом 106. В различных вариантах осуществления приложение 104 может быть различными типами приложений. Например, приложение 104 может быть приложением обработки текстов MICROSOFT® WORD®, системой связи MICROSOFT® OUTLOOK®, приложением электронной таблицы MICROSOFT® EXCEL®, приложением создания заметок MICROSOFT® ONENOTE® или другими типами приложений обработки текстов, приложений связи/электронной почты, приложений электронной таблицы, приложений создания заметок или другими типами приложений, которые позволяют пользователям взаимодействовать с документами. Соответственно, документ 106 может быть различными типами документов. Например, документ 106 может быть документом текстового процессора, веб-страницей, сообщением электронной почты, документом электронной таблицы или другим типом документа. В различных вариантах осуществления пользователь 102 может взаимодействовать с документом 106 различными способами. Например, в некоторых вариантах осуществления пользователь 102 может просматривать или редактировать содержимое документа 106.

[0028] Чтобы отобразить документ 106 пользователю 102, приложение 104 преобразует внутреннее представление документа 106 в документ, показанный пользователю 102. Например, представление документа 106 может включать в себя значительное количество данных, которые дают указание приложению 104, как отображать документ 106. Приложение 104 интерпретирует эти данные для отображения документа 106 пользователю 102. Однако эти данные обычно не отображаются пользователю 102.

[0029] Приложение 104 использует множество потоков, выполняемых вычислительной системой 100, чтобы дать пользователю 102 возможность взаимодействовать с документом 106. Поток является частью программы, которая может выполняться независимо от других частей программы. Потоки, используемые приложением 104, могут выполняться одновременно на разных блоках обработки вычислительной системы 100. Следовательно, два или более потоков могут попробовать одновременно обратиться к одним и тем же данным в представлении документа 106. Для двух или более потоков не желательно обращаться к одним и тем же данным одновременно, потому что могут возникнуть неожиданные результаты. Например, когда пользователь 102 предоставляет ввод в вычислительную систему 100 для замены старого слова (например, "tiger") в документе 106 новым словом (например, "leopard"), один поток обновляет подходящие данные в представлении документа 106 для замены старого слова новым словом. Одновременно другой поток проверяет орфографию в документе. Если бы проверяющий орфографию поток считывал подходящие данные, в то время как обновляющий поток обновлял подходящие данные, то проверяющий орфографию поток мог бы считать данные, представляющие некоторую часть нового слова (например, "leop"), и данные, представляющие некоторую часть старого слова (например, "ger"). Проверяющий орфографию поток мог бы увидеть слово "leopger" и указать, что новое слово написано неверно, даже если новое слово "leopard" написано правильно и выглядит правильным для пользователя 102. Это не является логически непротиворечивым.

[0030] Чтобы избежать этой ситуации, приложение 104 использует несколько представлений документа 106. Как проиллюстрировано в примере из фиг. 1, потоки включают в себя поток-конструктор 108. Как описано где-то в другом месте этого описания изобретения, поток-конструктор 108 изменяет документ 106 путем изменения активного представления документа 106. Активное представление документа 106 хранится в запоминающем устройстве вычислительной системы 100. После того, как поток-конструктор 108 завершает изменение активного представления документа 106, активное представление документа 106 становится неактивным представлением документа 106.

[0031] В дополнение к потоку-конструктору 108 приложение 104 использует один или несколько потоков-считывателей 110A-110N (вместе - "потоки-считыватели 110"). Потоки-считыватели 110 выполняют операции в отношении документа 106, используя одно или несколько неактивных представлений документа 106. Такие операции помогают приложению 104 предоставлять различные типы функциональных возможностей. Например, документ 106 может быть документом обработки текстов, например документом MICROSOFT® WORD®. В этом примере один из потоков-считывателей 110 выполняет операцию проверки орфографии над текстом в документе 106. В другом примере один из потоков-считывателей 110 получает документ 106, готовый для печати. В еще одном примере один из потоков-считывателей 110 сохраняет документ 106 в локальную или удаленную систему хранения данных. В еще одном примере один из потоков-считывателей 110 использует неактивное представление документа 106 для отображения документа 106 пользователю 102. В еще одном примере один из потоков-считывателей 110 изменяет нумерацию страниц документа 106, когда пользователь 102 набирает на клавиатуре данные в документ 106. В еще одном примере один из потоков-считывателей 110 идентифицирует места для вставки переносов, когда слова охватывают несколько строк.

[0032] Поток-конструктор 108 является единственным потоком, который изменяет данные в любом представлении документа 106. То есть потоки-считыватели 110 не изменяют активное представление документа 106 или любое неактивное представление документа 106. Точнее, потоки-считыватели 110 могут дать потоку-конструктору 108 указание изменить документ 106. Поток-конструктор 108 не изменяет никакие данные ни в одном неактивном представлении документа 106.

[0033] После того, как поток-конструктор 108 завершает операцию по изменению активного представления документа 106, активное представление документа 106 становится неактивным представлением документа 106. Это неактивное представление документа 106 доступно для использования потоками-считывателями 110. Чтобы снова изменить документ 106, поток-конструктор 108 формирует новое активное представление документа 106, изменяет то новое активное представление документа 106 и превращает это новое активное представление документа 106 в неактивное представление документа 106.

[0034] Поскольку никакой поток не изменяет никакое неактивное представление документа 106, то когда потоки-считыватели 110 считывают данные в неактивном представлении документа 106, логическая связность обеспечивается без блокирования каких-либо данных в неактивном представлении документа 106. Другими словами, отсутствует опасность, что другой одновременно выполняющийся поток мог бы записать в данные, пока один из потоков-считывателей 110 пытается считать те же данные.

[0035] Формирование полностью отдельных представлений документа 106 каждый раз, когда изменяется документ 106, могло бы потреблять огромное пространство в памяти вычислительной системы 100. Кроме того, формирование полностью отдельных представлений документа каждый раз, когда изменяется документ 106, могло бы потребовать больших объемов вычислений. Следовательно, активное представление документа 106 и неактивные представления документа 106 не включают в себя разные копии одних и тех же данных в запоминающем устройстве. Например, активное представление документа 106 и неактивное представление документа 106 могут оба включать в себя данные, которые представляет одну и ту же часть документа 106. В этом примере нет двух отдельных копий тех данных в запоминающем устройстве. Скорее, активное представление документа 106 и неактивное представления документа 106 ссылаются на одну и ту же копию тех данных в запоминающем устройстве.

[0036] Фиг. 2 иллюстрирует примерное дерево 200 документа и массив 202 элементов. Внутри документ 106 представляется в виде дерева документа, например дерева 200 документа. Дерево 200 документа является иерархией элементов документа. Эти элементы документа обычно не отображаются пользователю 102, а скорее используются приложением 104 для определения, как отобразить документ 106 пользователю 102.

[0037] Элементы документа в дереве 200 документа включают в себя элементы, которые представляют структуры внутри документа 106. Например, в примере из фиг. 2 дерево 200 документа включает в себя элемент 204 документа, который представляет документ 106 в целом. В этом примере дерево 200 документа включает в себя элемент 206 документа и элемент 208 документа, которые представляют абзацы в документе 106. Поскольку элемент 206 документа (то есть абзац) и элемент 208 документа (то есть другой абзац) представляют сущности внутри документа 106, элемент 206 документа и элемент 208 документа находятся ниже элемента 204 документа в дереве 200 документа.

[0038] Кроме того, в примере из фиг. 2 дерево 200 документа включает в себя элемент 210 документа, элемент 212 документа и элемент 214 документа. Элемент 210 документа и элемент 212 документа представляют последовательности текста в абзаце, представленном элементом 206 документа. Например, элементы 210 и 212 документа могут представлять предложения в абзаце, представленном элементом 206 документа. Поскольку элемент 210 документа и элемент 212 документа представляют сущности в абзаце, представленном элементом 206 документа, элемент 210 документа и элемент 212 документа находятся ниже элемента 206 документа в дереве 200 документа. Элемент 214 документа представляет последовательность текста в абзаце, представленном элементом 208 документа. Поскольку элемент 214 документа представляет сущность в абзаце, представленном элементом 208 документа, элемент 214 документа находится ниже элемента 208 документа в дереве 200 документа.

[0039] Элементы документа в дереве 200 документа могут обладать различными атрибутами. В примере из фиг. 2 элемент 204 документа может включать в себя атрибут, который устанавливает "Times New Roman" в качестве шрифта по умолчанию для документа 106. В этом примере элемент 208 документа может включать в себя атрибут, который переопределяет шрифт по умолчанию и устанавливает "Arial" в качестве шрифта для абзаца, представленного элементом 208 документа. Кроме того, в этом примере элемент 214 документа может включать в себя атрибут, который делает подчеркнутой последовательность текста, представленную элементом 214 документа.

[0040] На понятийном уровне память компьютера подобна строке сегментов. Каждый из сегментов в строке имеет разный адрес. Например, один сегмент в строке может иметь адрес "37", а следующий сегмент в строке может иметь адрес "38", и так далее. Каждый из сегментов может хранить данные. Поскольку память компьютера подобна строке сегментов, память компьютера на понятийном уровне является одномерной структурой. В отличие от этого, дерево 200 документа является двумерной структурой (то есть дерево 200 документа обладает высотой и шириной). Чтобы хранить дерево 200 документа (двумерную структуру) в памяти компьютера (одномерной структуре), необходимо представить дерево 200 документа как одномерную структуру.

[0041] Массив 202 элементов является примерной одномерной структурой, которая представляет дерево 200 документа. Массив 202 элементов содержит элементы 216A, 216B, 218A, 218B, 220A, 220B, 222A, 222B, 224A, 224B, 226A и 226B. Элементы 216A и 216B соответствуют элементу 204 документа в дереве 200 документа. Элемент 216A является открывающим элементом, а элемент 216B является закрывающим элементом, соответствующим элементу 216A. Элементы в массиве между открывающим элементом и соответствующим закрывающим элементом представляют элементы документа ниже элемента документа, представленного открывающим элементом и соответствующим закрывающим элементом.

[0042] Элементы в массиве 202 элементов между элементами 216A и 216B соответствуют элементам документа в дереве 200 документа ниже элемента 204 документа. Элементы 218A и 218B соответствуют элементу 206 документа в дереве 200 документа. Элементы в массиве 202 элементов между элементами 218A и 218B соответствуют элементам документа в дереве 200 документа ниже элемента 206 документа. Элементы 220A и 220B соответствуют элементу 210 документа в дереве 200 документа. Поскольку отсутствуют элементы документа в дереве 200 документа ниже элемента 210 документа, отсутствуют элементы в массиве 202 элементов между элементами 220A и 220B. Элементы 222A и 222B соответствуют элементу 212 документа в дереве 200 документа. Поскольку отсутствуют элементы документа в дереве 200 документа ниже элемента 210 документа, отсутствуют элементы в массиве 202 элементов между элементами 222A и 222B. Элементы 224A и 224B соответствуют элементу 208 документа в дереве 200 документа. Элементы в массиве 202 элементов между элементами 224A и 224B соответствуют элементам документа в дереве 200 документа ниже элемента 208 документа. Элементы 226A и 226B соответствуют элементу 214 документа в дереве 200 документа. Поскольку отсутствуют элементы документа в дереве 200 документа ниже элемента 214 документа, отсутствуют элементы в массиве 202 элементов между элементами 226A и 226B.

[0043] Когда пользователь 102 работает с документом 106, пользователь 102 может захотеть добавить новый абзац между абзацем, представленным элементом 206 документа, и абзацем, представленным элементом 208 документа. Следовательно, дерево 200 документа обновилось бы для включения в него нового элемента документа ниже элемента 204 документа. Новый элемент документа представляет новый абзац. Чтобы представить обновленное дерево 200 документа, потребовалось бы добавить новую пару элементов между элементами 218B и 224A в массиве 202 элементов. Новая пара элементов соответствует новому элементу документа.

[0044] Как упоминалось ранее, память компьютера на понятийном уровне является строкой сегментов. Данные, представляющие массив 202 элементов, сохраняются в таких сегментах в памяти компьютера. Чтобы вставить новые элементы между двумя элементами в массиве 202 элементов, поток-конструктор 108 мог бы освободить сегменты для новых элементов путем копирования всех элементов в массиве 202 элементов после новых элементов в сегменты еще ниже по строке сегментов, а затем сохранения новых элементов в освободившиеся сегменты. Например, элемент 218B можно сохранить в сегменте "37", элемент 224A можно сохранить в сегменте "38", элемент 226A можно сохранить в сегменте "39", элемент 226B можно сохранить в сегменте "40", элемент 224B можно сохранить в сегменте "41", а элемент 216B можно сохранить в сегменте "41". В этом примере, чтобы вставить элементы между элементом 218B и элементом 224A, вычислительная система 100 могла бы скопировать элемент 216B в сегмент "43", элемент 224B в сегмент "42", элемент 226B в сегмент "41", элемент 226A в сегмент "40" и элемент 224A в сегмент "39". В этом примере поток-конструктор 108 затем мог бы сохранить новые элементы в сегментах "37" и "38". Как демонстрирует этот пример, если бы поток-конструктор 108 должен был использовать этот подход, то потоку-конструктору 108 могло бы потребоваться выполнить большое количество операций копирования, чтобы вставить элементы в массив 202 элементов. Аналогичным образом, если бы поток-конструктор 108 должен был сдвинуть элементы в массиве 202 элементов, когда элементы удаляются из массива 202 элементов, то потоку-конструктору 108 могло бы потребоваться выполнить большое количество операций копирования, чтобы удалить элементы из массива 202 элементов.

[0045] Вместо копирования элементов, когда в массив 202 элементов вставляется новый элемент, поток-конструктор 108 добавляет новый элемент в один конец реального массива элементов. Следовательно, элементы в реальном массиве элементов не обязательно упорядочены так, что элементы, соответствующие элементу документа ниже другого элемента документа, находятся между элементами, соответствующими другому элементу документа. Как описано в этом описании изобретения, представление документа 106 содержит дерево индексов, таблицу дескрипторов фрагментов и такой реальный массив элементов. Дерево индексов и таблица дескрипторов фрагментов указывают, где элементы в реальном массиве элементов находятся в виртуальном массиве элементов. Виртуальный массив элементов является одномерным представлением дерева 200 документа. Элементы в виртуальном массиве элементов упорядочены так, что элементы, соответствующие элементу документа ниже другого элемента документа, находятся между элементами, соответствующими другому элементу документа.

[0046] Фиг. 3 - блок-схема, иллюстрирующая примерное представление документа 106. Представление документа 106 включает в себя дерево 300 индексов, таблицу 302 дескрипторов фрагментов и реальный массив 304 элементов. Дерево 300 индексов и таблица 302 дескрипторов фрагментов являются структурами данных, которые указывают, где элементы в реальном массиве 304 элементов находятся в виртуальном массиве 306 элементов.

[0047] Как проиллюстрировано в примере из фиг. 3, реальный массив 304 элементов содержит элементы 308A, 308B, 310A, 310B, 312A и 312B. Элементы 308A, 308B, 310A, 310B, 312A и 312B соответствуют каждому элементу документа в дереве документа 106. Для каждого заданного элемента в виртуальном массиве 306 элементов, если заданный элемент находится между открывающим элементом и закрывающим элементом в виртуальном массиве 306 элементов, то заданный элемент представляет элемент документа в дереве документа, который находится ниже элемента документа в дереве документа, представленном открывающим элементом и закрывающим элементом. Виртуальный массив 306 элементов также содержит элементы 308A, 308B, 310A, 310B, 312A и 312B. Однако виртуальный массив 306 элементов фактически не существует в памяти компьютера.

[0048] В некоторых вариантах осуществления, например, проиллюстрированных в примере из фиг. 3, элементы в реальном массиве 304 элементов упорядочены должным образом, когда приложение 104 первоначально загружает документ 106. Другими словами, каждый элемент в реальном массиве 304 элементов, соответствующий элементу документа ниже другого элемента документа, находится между элементами, соответствующими другому элементу документа. Следовательно, когда приложение 104 первоначально загружает документ 106, реальный массив 304 элементов может быть таким же, как и виртуальный массив 306 элементов.

[0049] Таблица 302 дескрипторов фрагментов содержит набор из одного или нескольких дескрипторов фрагментов. Каждый из дескрипторов фрагментов в таблице 302 дескрипторов фрагментов является структурой данных, которая идентифицирует разный фрагмент реального массива 304 элементов. Фрагмент реального массива 304 элементов является набором из одного или нескольких последовательных элементов в реальном массиве 304 элементов. Например, элементы 308A, 310A и 310B могли бы быть фрагментом реального массива 304 элементов, а элементы 312B и 308B могли бы быть другим фрагментом реального массива 304 элементов.

[0050] В различных вариантах осуществления дескрипторы фрагментов реализуются различными способами. Например, в некоторых вариантах осуществления дескрипторы фрагментов задают реальное смещение крайнего левого элемента фрагмента и реальное смещение крайнего правого элемента фрагмента. В этом описании изобретения элемент в массиве считается находящимся слева от другого элемента в массиве, когда элемент находится ближе к началу массива, нежели другой элемент. Аналогичным образом элемент в массиве считается находящимся справа от другого элемента в массиве, когда элемент находится дальше от начала массива, нежели другой элемент. В других вариантах осуществления дескрипторы фрагментов реализуются в виде структур данных, имеющих атрибут реального смещения и атрибут длины. Реальное смещение элемента указывает расстояние от начала реального массива 304 элементов до этого элемента. Атрибут реального смещения у дескриптора фрагмента указывает реальное смещение крайнего левого элемента во фрагменте. Атрибут длины у дескриптора фрагмента указывает длину фрагмента. Эта реализация дескрипторов фрагментов используется по всему описанию изобретения. Однако следует понимать, что в других вариантах осуществления могут использоваться другие реализации дескрипторов фрагментов.

[0051] Атрибут реального смещения у дескриптора фрагмента может указывать реальное смещение различными способами. Например, в некоторых вариантах осуществления атрибут реального смещения может указывать количество байтов от начала реального массива 304 элементов до элемента. В других вариантах осуществления атрибут реального смещения может указывать количество элементов между началом реального массива 304 элементов и элементом. Варианты осуществления, где атрибут реального смещения указывает количество элементов, описываются по всему данному описанию изобретения. Однако следует понимать, что в других вариантах осуществления атрибуты реального смещения могут указывать расстояния от начала реального массива 304 элементов другими способами.

[0052] Атрибут длины у дескриптора фрагмента может указывать длину фрагмента различными способами. Например, в некоторых вариантах осуществления атрибут длины может указывать количество байтов во фрагменте. В других вариантах осуществления атрибут длины может указывать количество элементов во фрагменте. Варианты осуществления, где атрибуты длины указывают количества элементов, описываются по всему данному описанию изобретения. Однако следует понимать, что в других вариантах осуществления атрибуты длины могут указывать длины фрагментов другими способами.

[0053] Когда вычислительная система 100 первоначально загружает документ 106, имеется только один фрагмент в реальном массиве 304 элементов. Следовательно, таблица 302 дескрипторов фрагментов включает в себя единственный дескриптор 314 фрагмента. Дескриптор 314 фрагмента имеет атрибут реального смещения, равный 0, посредством этого указывая фрагмент, который начинается в начале реального массива 304 элементов. Дескриптор 314 фрагмента имеет атрибут длины, равный 6, указывающий, что фрагмент имеет длину в шесть элементов.

[0054] Дерево 300 индексов содержит иерархию одного или нескольких индексных узлов. Каждый из индексных узлов в дереве 300 индексов соответствует разному дескриптору фрагмента в таблице 302 дескрипторов фрагментов. Как проиллюстрировано в примере из фиг. 3, имеется только один дескриптор 314 фрагмента в таблице 302 дескрипторов фрагментов. Следовательно, дерево 300 индексов содержит единственный индексный узел 316.

[0055] В различных вариантах осуществления индексные узлы в дереве 300 индексов реализуются различными способами. Например, в некоторых вариантах осуществления индексные узлы в дереве 300 индексов реализуются в виде структур данных, имеющих атрибут левого потомка, атрибут правого потомка и атрибут дескриптора. В таких вариантах осуществления, если индексный узел имеет левый дочерний индексный узел в дереве 300 индексов, то атрибут левого потомка у индексного узла указывает левого потомка индексного узла. Если индексный узел имеет правый дочерний индексный узел в дереве 300 индексов, то атрибут правого потомка у индексного узла указывает правого потомка индексного узла. Атрибут дескриптора у индексного узла указывает дескриптор фрагмента в таблице 302 дескрипторов фрагментов. В примере из фиг. 3 атрибут дескриптора у индексного узла 316 указывает дескриптор 314 фрагмента. Варианты осуществления, где индексные узлы реализуются в виде структур данных, имеющих атрибуты левого потомка, атрибуты правого потомка и атрибуты дескриптора, описываются по всему данному описанию изобретения. Однако следует принять во внимание, что в других вариантах осуществления индексные узлы реализуются другими способами.

[0056] Фиг. 4 - блок-схема, иллюстрирующая примерное представление документа 106, когда вставляются элементы. Как проиллюстрировано в примере из фиг. 4, элементы 402A, 402B, 404A и 404B вставляются в один конец реального массива 304 элементов. Элементы 402A и 402B представляют элемент документа, который находится ниже элемента документа, представленного элементами 310A и 310B. Элементы 404A и 404B представляют элемент документа, который находится ниже элемента документа, представленного элементами 310A и 310B. Следовательно, в виртуальном массиве 306 элементов элементы 402A, 402B, 404A и 404B находятся между элементами 310A и 310B.

[0057] Заранее все элементы в реальном массиве 304 элементов были упорядочены должным образом. Следовательно, только один дескриптор 314 фрагмента был нужен для указания фрагмента реального массива 304 элементов, который включал в себя элементы между элементами 308A и 308B. Когда элементы 402A, 402B, 404A и 404B вставляются в реальный массив 304 элементов, элементы в реальном массиве 304 элементов уже не упорядочены должным образом. Вместо этого элементы в реальном массиве 304 элементов разделяются на три фрагмента: фрагмент реального массива 304 элементов, содержащий элементы, которые находятся слева от элементов 402A, 402B, 404A и 404B (то есть элементы 308A и 310A), фрагмент реального массива 304 элементов, содержащий элементы 402A, 402B, 404A и 404B, и фрагмент реального массива 304 элементов, содержащий элементы, которые находятся справа от элементов 402A, 402B, 404A и 404B (то есть элементы 310B, 312A, 312B и 308B).

[0058] Свойством таблицы 302 дескрипторов фрагментов является то, что значения атрибутов дескрипторов фрагментов нельзя изменить. Это свойство может гарантировать, что потоки-считыватели 110 могут считывать данные из дескрипторов фрагментов без необходимости учета вероятности, что поток-конструктор 108 может изменять данные в дескрипторах фрагментов, пока потоки-считыватели 110 считывают данные в дескрипторах фрагментов.

[0059] Поскольку значения атрибутов дескрипторов фрагментов не изменяются, а дескриптор фрагмента может указывать только одиночный фрагмент в реальном массиве 304 элементов, нужны дополнительные дескрипторы фрагментов. Чтобы добавить дополнительные дескрипторы фрагментов, поток-конструктор 108 формирует дескриптор 406 фрагмента, дескриптор 408 фрагмента и дескриптор 410 фрагмента. Дескриптор 406 фрагмента, дескриптор 408 фрагмента и дескриптор 410 фрагмента составляют активную версию таблицы 302 фрагментов. Активная версия таблицы 302 фрагментов является частью активного представления документа 106.

[0060] Дескриптор 406 фрагмента заменяет дескриптор 314 фрагмента. Однако поток-конструктор 108 сразу не удаляет дескриптор 314 фрагмента. Наоборот, дескриптор 314 фрагмента продолжает существовать как часть неактивной версии таблицы 302 фрагментов в неактивном представлении документа 106. Следовательно, потоки-считыватели 110 могут использовать дескриптор 314 фрагмента, пока поток-конструктор 108 выполняет операции над дескрипторами фрагментов в активной версии таблицы 302 дескрипторов фрагментов.

[0061] Дескриптор 406 фрагмента идентифицирует фрагмент реального массива 304 элементов, содержащий элементы 308A и 310A. Отметим, что дескриптор 406 фрагмента является клоном (то есть копией) дескриптора 314 фрагмента за исключением того, что атрибут длины у дескриптора 406 фрагмента отличается от атрибута длины у дескриптора 314 фрагмента. Дескриптор 408 фрагмента идентифицирует фрагмент реального массива 304 элементов, содержащий элементы 310B, 312A, 312B и 308B. Дескриптор 410 фрагмента идентифицирует фрагмент реального массива 304 элементов, содержащий элементы 402A, 402B, 404A и 404B.

[0062] Индексные узлы в дереве 300 индексов могут иметь вплоть до двух дочерних узлов. Высоты двух поддеревьев индексного узла в дереве 300 индексов отличаются не более чем на единицу. Например, глубина правого поддерева индексного узла не может быть равна 3, когда глубина левого поддерева индексного узла равна 1. В другом примере глубина правого поддерева индексного узла может быть равна 2, 1 или 0, когда глубина левого поддерева равна 1. В некоторых вариантах осуществления дерево 300 индексов является деревом AVL, B-деревом, красно-черным деревом или другим видом двоичного дерева.

[0063] Дерево 300 индексов обладает свойством сортировки. Свойство сортировки предусматривает, что для каждого индексного узла в дереве 300 индексов элементы, ассоциированные с индексными узлами в левом поддереве индексного узла, имеют виртуальные смещения меньше виртуальных смещений элементов, ассоциированных с индексным узлом. Кроме того, элементы, ассоциированные с индексными узлами в правом поддереве индексного узла, имеют виртуальные смещения больше виртуальных смещений элементов, ассоциированных с индексным узлом. Элемент ассоциируется с индексным узлом, когда элемент находится во фрагменте, указанном дескриптором фрагмента, указанным индексным узлом. Виртуальное смещение элемента является расстоянием от начала виртуального массива 306 элементов до положения элемента в виртуальном массиве 306 элементов.

[0064] К тому же свойством дерева 300 индексов является то, что значения атрибутов индексных узлов нельзя изменять. Это свойство может гарантировать, что потоки-считыватели 110 могут считывать данные из индексных узлов без необходимости учета вероятности, что поток-конструктор 108 может изменять данные в индексных узлах, пока потоки-считыватели 110 считывают данные в индексных узлах.

[0065] Для поддержания этих свойств поток-конструктор 108 формирует индексные узлы 412, 414 и 416, когда элементы 402A, 402B, 404A и 404B вставляются в реальный массив 304 элементов. Индексные узлы 412, 414 и 416 составляют активную версию дерева 300 индексов. Активная версия дерева 300 индексов является частью активного представления документа 106.

[0066] Индексный узел 414 заменяет индексный узел 316. Однако поток-конструктор 108 сразу не удаляет индексный узел 316. Наоборот, индексный узел 316 продолжает существовать как часть неактивной версии дерева 300 индексов, включенной в неактивное представление документа 106. Следовательно, потоки-считыватели 110 могут использовать индексный узел 316, пока поток-конструктор 108 выполняет операции для изменения активной версии дерева 300 индексов. Индексный узел 412 указывает дескриптор 406 фрагмента, индексный узел 414 указывает дескриптор 410 фрагмента, а индексный узел 416 указывает дескриптор 408 фрагмента.

[0067] Индексный узел 412 находится в левом поддереве индексного узла 414. Следовательно, индексный узел 412 ассоциируется с элементами, имеющими виртуальные смещения, которые меньше виртуальных смещений элементов, ассоциированных с индексным узлом 414. Индексный узел 416 находится в правом поддереве индексного узла 414. Следовательно, индексный узел 416 ассоциируется с элементами, имеющими виртуальные смещения больше виртуальных смещений элементов, ассоциированных с индексным узлом 414.

[0068] В примере из фиг. 4 активное представление документа 106 включает в себя активную версию дерева 300 индексов, активную версию таблицы 302 дескрипторов фрагментов и реальный массив 304 элементов. Когда поток-конструктор 108 завершает операцию для вставки элементов 402A, 402B, 404A и 404B, активная версия дерева 300 индексов включает в себя индексные узлы 412, 414 и 416, а активная версия таблицы 302 дескрипторов фрагментов включает в себя дескрипторы 406, 408 и 41