Індекси на основі B-дерев для підтримки високого темпу оновлень, Інші СУБД, Бази даних, статті

Переклад: Сергій Кузнецов


Передмова перекладача


Стаття Грейф привернула мене тим, що вже давно не попадалися огляди, присвячені алгоритмам роботи з B-деревами. Повинен відразу сказати, що багато в чому стаття не виправдала мої очікування: багато хто, мабуть, цікаві методи і структури даних описані занадто коротко і сумбурно, дуже не вистачає ілюстрацій. Під час перекладу мені постійно хотілося виправити недоліки статті, благо, що більша частина джерел, згадуються в списку літератури, вільно доступна в Internet. Однак я стримав себе і представляю вам чистий переклад статті. В цілому він дає уявлення про існуючі підходи, а з подробицями ви можете при бажанні ознайомитись самі, скориставшись списком літератури та поставленими мною посиланнями на публікації в Web.

1. Анотація


У деяких додатках збір даних домінує над обробкою даних. Наприклад, при моніторингу рухомих об’єктів часто потрібно більше операцій вставки, оновлення, ніж запитів. Це дисбаланс часто демонструється при зборі даних з використанням автоматичних сенсорів. У більш широкій постановці, невирішеною проблемою є індексування потоків.

Для цих додатків хорошим варіантом є індекси на основі B-дерев, якщо прийняти деякі компромісні рішення, спрямовані на оптимізацію швидше операцій оновлення, ніж запитів. У цій статті наводиться огляд деяких методів, які за рахунок зниження ефективності обробки запитів дозволяють B-деревах витримувати дуже високий темп оновлень, на кілька порядків вищий, ніж можуть допустити традиційні B-дерева. Не дивно, що деякі з цих методів нагадують методи, використовувані при створенні, розбудові індексів і т.д., а інші виводяться з відомих технологій, таких як диференціальні файли та файлові системи з журнальної структурою (log-structured file system).

2. Введення


Деякі програми більшою мірою збирають дані, чим обробляють запити до них. Наприклад, система управління автопарком компанії вантажних автомобільних перевезень або таксі може реєструвати дані про поточну позиції рухається засоби набагато частіше, ніж позиції автомобілів запитуються диспетчерів автопарку. У цих випадках організацію індексу і B-дерева, на відміну від традиційного підходу, слід оптимізувати з метою підвищення ефективності виконання операцій вставки, оновлення, а не запитів.

Інший областю застосування методів, що обговорюються в цьому огляді, є індексування безперервних потоків даних. Досить добре зрозуміла фільтрація потоків “на льоту”, але для потоків, що містять ідентифікатори об’єктів реального світу, часто потрібно зіставлення зі статичними даними, а також з іншими потоками. Тому вкрай необхідна можливість збору потокових даних, зазвичай в порядку їх надходження, а також їх індексування по атрибутам, відмінним від часу надходження. Іноді потрібно кілька індексів, що підтримують різні порядки. Наприклад, для забезпечення ефективного і близького до миттєвого виявлення випадків шахрайства в потоці даних про транзакції з кредитними картками може знадобитися індексування за номером картки, ідентифікаційним даними клієнта (клієнт може втратити кілька кредитних карт в один і той же час) і даними про продавця (нечесний службовець може шахрайським чином розплачуватися кредитними картами багатьох клієнтів).

Далі ми припускаємо, що ефективність операцій оновлення і вставки є більш важливою, ніж ефективність обробки запитів. Якщо читача не цікавлять такі додатки, то до його B-деревах слід застосовувати традиційні оптимізаційні методи, а не методи, розглянутих у цій статті. Крім того, ми припускаємо, вже застосовано-яка регулювання робочого навантаження, наприклад, вироблена “найкраща” політика реєстрації даних про поточне місцезнаходження автомобілів, так що залишилися запити на оновлення дійсно повинні бути відображені в усіх розглянутих індексах. Нарешті, ми припускаємо, що враховується можливість апаратної підтримки, і вона використовується, наскільки це можливо і доцільно, наприклад, використовуються розшарування дисків і твердотільні диски або дискові буфера.

3 Оптимізація введення / виводу


Як і в більшості операцій баз даних, фокусування на ефективності дискових операцій вводу / виводу є дієвим способом підвищення продуктивності і масштабованості. Однак необхідно розділяти вдосконалення загальної пропускної спроможності системи та скорочення часу відгуку окремих транзакцій, що може бути дуже цікаво в даному випадку, а може бути і зовсім не цікаво.

Є кілька дуже загальних технологій вдосконалення продуктивності, наприклад, стиснення даних [WKH 00]. У робочих навантаженнях з інтенсивним оновленням даних істотне стиснення застосовується не тільки до даних, а й до журналу транзакцій. Тут достатньо зауважити, що деякі методи стиснення є дивно простими, наприклад, відкидання лідируючих або хвостових нулів або прогалин і об’єднання кількох журнальних записів від однієї транзакції в одну журнальну запис для скорочення накладних витрат, викликаних наявністю в журналі транзакцій множинних заголовків записів.

3.1 Попередня вибірка, випереджаюче читання і відкладений запис

Відкладена запис (write-behind) сторінок журналу і даних є добре відомим методом. Сама по собі відкладений запис не підвищує пропускну здатність системи, оскільки обсяг записи не скорочується. Однак відкладений запис часто забезпечує можливість запису даних великого обсягу, що є ще більш ефективним, ніж підтримка черг введення / виведення. Крім того, відкладений запис корисна в разі піків робочого навантаження і дозволяє виробляти додаткову оптимізацію. Наприклад, в сучасних дискових пристроях підтримуються власні черги команд, і обміни виконуються краще, якщо завжди є десятки чекають операцій введення / виводу [ADR 03].

Попереджуюче читання (read-ahead, зазвичай використовується при скануванні) не застосовується до операцій оновлення, але воно застосовується для приєднання всієї гілки модифікацій до існуючого B-дереву. При злитті кількох розділів B-дерева (обговорюваному нижче) в один розділ випереджаюче читання з використанням прогнозування може поліпшити продуктивність, оскільки злиття розділів, по суті, являє ту ж проблему, що і злиття прогонів при виконанні зовнішньої сортування зі злиттям [G 03a]

Попередня вибірка (prefetch), заснована на індивідуальних ключах, застосовується не тільки до операцій вибірки, наприклад, при пересуванні з некластеризованих індексу в кластеризованих індекс, але і до операцій оновлення. Однак, подібно читання, і відкладеного запису, попередня вибірка також не призводить до безпосереднього поліпшення продуктивності або пропускної здатності системи, а лише зменшує час реакції або затримку виконання окремих операцій, що може непрямим чином привести до підвищення продуктивності за рахунок скорочення конкуренції при управлінні паралельним виконанням операцій.

3.2 B-дерева, оптимізовані для запису

На додаток до асинхронного вводу-виводу, ефективність операцій запису може бути покращена за рахунок динамічного розміщення вмісту на диску [G 04]. Цей ефект добре відомий і інтенсивно досліджувався для файлових систем з журнальної структурою [OD 89], зокрема, в контексті RAID-сховищ [PGK 88]. Основна ідея B-дерев, оптимізованих для запису, полягає у виділенні нового місця на диску при кожного запису сторінки на диск при виконанні операції запису, тобто пізніше прийняття рішення менеджером буферів про заміщення буфера. При цьому нове місце для сторінки виділяється таким чином, що кілька паралельних операцій запису націлюється на одну і ту ж область диска.

Щоб уникнути подальшого оновлення сусідніх сторінок, традиційна ланцюжок сторінок з використанням фізичних ідентифікаторів сторінок замінюється логічним ланцюжком сторінок з використанням розділових ключів (separator key), тобто кожна сторінка несе в якості нижнього і верхнього бар’єрів розділовий ключ, копійований в сторінку батьківського вузла при отщеплении сторінки від її сусідів. На додаток до підтримки тих же перевірок узгодженості та інших технічних операцій, що і ті, які підтримуються традиційними фізичними ланцюжками сторінок, бар’єрні ключі спрощують та покращують блокування діапазонів значень ключа, оскільки ніколи не потрібно переміщатися до сусідньої листовий сторінці для знаходження правого значення ключа в діапазоні. Після заміни фізичних ланцюжків сторінок логічними бар’єрними ключами фізичні ідентифікатори сторінок залишаються тільки в покажчиках дітей, і тільки їх потрібно змінювати при переміщенні вузла на нове місце на диску.

У традиційних алгоритмів B-дерев нове місце виділяється при прийнятті рішення менеджером B-дерева про розщеплення вузла, так що в наступних журнальних записах можуть бути посилання на ідентифікатор цієї сторінки. В B-деревах, оптимізованих для запису, новій сторінці дається тимчасовий ідентифікатор, який може використовуватися в журнальних записах, і сторінка переміщається при виконанні операції запису, що дуже нагадує переміщення сторінки при виконанні дефрагментації B-дерева. Тому застосовуються випробувані механізми управління паралельним виконанням операцій і відновлення.

Вплив на продуктивність B-дерев, оптимізованих для запису, полягає в тому, що випадкові операції запису перетворюються у великі послідовні операції запису, що забезпечують підвищення пропускної здатності більш ніж в 10 разів ціною додаткової підтримки батьків кожного вузла при кожній його записи на нове місце на диску.

4. Буферизація вставок


Є декілька способів буферизації і угруповання нових вставок з метою зменшення частоти оновлення кожного вузла B-дерева, що, в свою чергу, призводить до зменшення інтенсивного дискового введення-виведення, обмінів з кешем центрального процесора і т.д. При виконанні запитів доводиться або робити пошук в буферній структурі на додаток до пошуку в індексі B-дерева, або втискати всі або деякі буферні запис в індекс B-дерева.

Для коректного транзакційного виконання потрібно журналізіровать і вставки, і видалення в буфері; тому обсяг журналу може перевершувати об’єм традиційного журналу більш ніж в три рази. Однак користувальницької транзакцією є тільки вихідна вставка в перший буфер, а всі наступні переміщення записи можуть бути системними транзакціями, які можна фіксувати дешевим чином без виштовхування заключній частини журналу в стабільну пам’ять.

4.1 Буферизація в межах блоків дерева

Деякі дослідники аналізували структури даних і алгоритми, що додають великий буфер до кожного внутрішнього вузла дерева [A 96, AHV 02, VSW 97]. Часто розмір цього буфера перевищує розмір області, призначеної для традиційних пар “ключ-покажчик”, не тільки тому, що кожна буферизованная новий запис більше пари “ключ-покажчик”, але також і тому, що число зберігаються записів може бути більше числа пар “ключ-покажчик”. Коли буфер повністю заповнюється, відповідні записи виштовхуються в його дитини з найбільшим числом зберігаються записів.

Як здається, записи повинні утримуватися тільки для тих дітей, які не перебувають безпосередньо в буфері вводу-виводу. На основі того, що в більшості B-дерев є не менше ста гілок, що в більшості серверів баз даних розмір пам’яті перевершує 1% розміру диска, і що обговорювані тут B-дерева є найбільш активно використовуються і критично впливають на продуктивність індексами усередині бази даних, можна зробити висновок, що така буферизація застосовна тільки до вузлів, що є безпосередніми предками листя. Іншими словами, можуть бути можливі додаткові удосконалення опублікованих методів, що дозволяють буферизують вузли всіх рівнів B-дерева.

4.2 Буферизація в окремих структурах

Альтернативою буферизації вставок у вузлах дерева є створення окремої структури даних для буферизації нових вставок [LJB 95, MOP 00, OCG 96]. Ця структура даних може бути ще одним B-деревом або може представляти іншу різновид структури даних в основній пам’яті, наприклад, хеш-таблицю. Насправді, вона може бути і набором структур даних, що утворюють ієрархію або каскад областей зберігання. Цікаво, що ця організація нагадує обидві організації, що пропонувалися збірку сміття за їхніми [U 84].

Використання нових структур передбачає наявність нових механізмів для управління паралельним виконанням операцій і відновлення. Таким чином, кращим механізмом була б вже реалізована індексна структура. В іншому випадку для нових моделей або протоколів блокування потрібні докази коректності, реалізація, тестування і т.д. Можливо, в найбільш бажаною реалізації повинні уникати і окремі структури, і модифікації існуючих структур, а замість цього існуючі механізми повинні використовуватися іншим чином.

4.3 Буферизація в розділах B-дерева

В одній з робіт, мотивуватися бажанням уникнути кодування окремих випадків, використовується основне B-дерево як власна буферна структура даних за рахунок введення розділів усередині кожного B-дерева [G 03a]. За рахунок введення штучного лідируючого стовпця ключа зберігається традиційна структура B-дерева. “Основне” B-дерево визначається загальним значенням штучного лідируючого стовпця ключа, скажімо, 0 або null, а один чи більше буферів визначаються іншими значеннями цього стовпчика, скажімо, 1, 2 і т.д.

Традиційне управління буферами разом з обмеженнями на розмір заново доданих розділів забезпечують, що вставки даних користувача транзакціями можуть повністю відбуватися в основній пам’яті. У граничному випадку розділи нових вставок можуть складатися з одного запису, тобто кожна вставка визначає новий розділ і, таким чином, може виконуватися практично без пошуку або реорганізації сторінки всередині B-дерева. Таким чином, максимізується швидкість вставок і пропускна здатність користувацьких транзакцій за рахунок потреби великих зусиль для оптимізації та реорганізації індексу.

При виконанні запитів потрібно робити пошук в кожному розділі з використанням традиційних методів, що обмежують значення деяких стовпців індексу, за винятком лідируючого [LJB 95], які, можливо, доповнюються оптимізацією на основі того факту, що в якості ідентифікаторів розділів використовуються послідовні цілі значення. В якості альтернативи, при виконанні запитів можуть виникати деякі злиття, що виконуються до реальної вибірки даних і реалізуються з використанням системних транзакцій. Таким чином, робота по підтримці B-дерева, традиційно виконувана як частина операцій оновлення, переміщується до складу операцій запитів або реорганізації, яка може траплятися в будь-який час між вставкою і запитом. В крайньому випадку, запит може привести до повного злиття і оптимізації всіх розділів за винятком, може бути, одного розділу, призначеного для поточних вставок.

Деякі цікаві аспекти таких B-дерев полягають у тому, що


  1. операція реорганізації, яка об’єднує кілька розділів в один розділ, дуже схожа на крок злиття в традиційній зовнішньої сортуванні зі злиттям;
  2. такі операції злиття можуть виконуватися як системні транзакції і фіксувати кожен раз дуже невеликий діапазон ключів;
  3. такі операції злиття та реорганізації можуть припинятися і відновлюватися в будь-який час, якщо виникають періоди пікового навантаження;
  4. той же метод може сприяти виконанню масових вилучень, тобто видаляються елементи B-дерева переміщуються невеликими системними транзакціями у виділений розділ, а потім віддаляються в одній з швидких користувацьких транзакцій, яка вирізає з B-дерева кілька повних сторінок.

4.4 Плавне зниження ефективності

Крім загального підвищення продуктивності, буферізованние вставки забезпечують плавне зниження ефективності в разі хибних оцінок потужності в ході оптимізації запитів. Сьогодні при оптимізації запитів можна вибирати між обробкою операцій оновлення в режимі “рядок-за-рядком” і обробкою в режимі “індекс-за-індексом”. При виконанні операції оновлення в режимі “рядок-за-рядком” оновлення всіх потрібних індексів здійснюється відразу після поновлення черговий рядка. Оновлення в режимі “індекс-за-індексом” означає, що до кожного індексу відразу застосовуються всі оновлення, можливо, після розщеплення кожної операції модифікації на відповідну пару операцій видалення та вставки, сортування змін за значеннями ключа індексу і рекомбінірованія змін, якщо це виявляється доречним. Узагальнена версія методів, описаних в [GKK 01], реалізується Microsoft SQL Server, починаючи з випуску 7.0. Оновлення в режимі “рядок-за-рядком” найбільш доречні для невеликих змін, наприклад, при оперативній обробці транзакцій, в оновлення в режимі “індекс-за-індексом” є більш ефективними для великих оновлень, особливо таких, які зачіпають не тільки листові сторінки індексів, наприклад, масових вставок або вилучень. Для забезпечення плавного зниження ефективності план виконання може наказувати обробку оновлення в режимі “рядок-за-рядком” при очікуваному невеликому безлічі оновлень, а при реальному виконанні можна виявити, що безліч оновлень є набагато більшим, і перемкнутися на режим виконання “індекс-за-індексом”.

Описані вище буферізованние вставки з використанням розділених B-дерев є третій спосіб застосування оновлень до індексу на основі B-дерева, і тим самим забезпечують ще один варіант плавного зниження ефективності. Обробка в режимі “рядок-за-рядком”, націлена на новий розділ, обіцяє кращі модель введення / виводу і продуктивність, ніж ті, які забезпечуються при обробці в режимі індекс-за-індексом, хоча при цьому зберігається недолік неоптимальності індексів. Для забезпечення плавного зниження ефективності план виконання операції оновлення може передбачати виконання оновлення в режимі “рядок-за-рядком” в головному розділі до тих пір, поки не з’ясується реальний розмір безлічі оновлень, а потім перемикання на буферізованние або розділені оновлення. Хоча можна реалізувати плавне зниження ефективності шляхом зміни режиму “рядок-за-рядком” на режим “індекс-за-індексом” з використанням умовного виконання в традиційному плані виконання запиту, призначення індексним змін нового ідентифікатора розділу (штучного лідируючого стовпця ключа) є набагато простішим дією і сприяє підвищенню ефективності оновлення.

5. Диференціальні файли та індекси


Хоча методи, що обговорювалися в попередньому розділі, придатні для буферизації вставок, вони не дозволяють буферизують інші операції оновлення, тобто модифікації і видалення. Однак, ці методи можна розширити шляхом адаптації до B-деревах ідей з області диференціальних файлів [SL 76]. Цікаво, що деякі адаптації B-дерев для версійність управління паралельним виконанням операцій і для історичних індексів є дуже схожими, включаючи логіку, необхідну протягом обробки запитів.

Основний підхід полягає в додаванні записів, які роблять недійсними попередні записи, без реальної зміни цих попередніх записів. При оновленні новий запис заміщає попередній елемент B-дерева з тим же ключем. При видаленні заново додається запис просто вказує на кінець історії даного ключа, або, по крайней мере, на кінець історії до тих пір, поки згодом не відбудеться нова вставка з тим же ключем.

При виконанні запитів потрібно шукати в історії кожного конкретного ключа або його поточний стан (при традиційній семантиці запитів), або стан в заданий час (при обробці історичних запитів, прив’язаних до точки в часі). Історію ключів можна ущільнювати за допомогою операцій злиття, в залежності від бажаних можливостей майбутніх запитів.

Іншими словами, подібно буферизують вставкам, буферізованние модифікації і видалення в диференціальних B-деревах жертвують ефективністю запитів на користь ефективності оновлення. Перетворення випадкових вставок, видалень і модифікацій по одному запису в операції додавання з використанням великих послідовних операцій запису обіцяє підвищення пропускної здатності обробки оновлень на два порядки.

Звичайно, є також взаємозв’язок між диференціальними файлами і реалізацією версійність ізоляції на основі миттєвих знімків (multi-version snapshot isolation). Однак основне розходження полягає в тому, що в диференціальних файлах зберігається найстаріша версія плюс набір “дельт” в прямому часу, а реалізації версійність ізоляції на основі миттєвих знімків зазвичай орієнтовані на забезпечення доступу до найбільш свіжим версіями, тобто в них звичайно зберігається найбільш свіжа версія плюс набір “дельт” в зворотному часу.

6. Гарантії транзакцій


Ще одна можливість поліпшення продуктивності може грунтуватися на ослабленні транзакційних гарантій для деяких індексів, зокрема, для надлишкових некластеризованих індексів. Ми розглянемо три методи: ослаблення поділу індивідуальних транзакцій за рахунок пакетування; ослаблення гарантій у разі системних збоїв; запис змін тільки в журнал транзакції без спроб їх застосування до індексом з неявній небезпекою того, що спроба застосування таких змін в більш пізній час може закінчитися невдачею. Очевидно, що ці методи застосовуються лише в тих випадках, коли залишилися транзакційні гарантії є досить суворими для наявних додатків.

6.1 Операції тільки над журналом

Якщо операції підтримки індексу не можуть впоратися з потоком оновлень, може бути, їх вдасться хоча б зареєструвати в журналі транзакцій. В цьому випадку можна було б розміщувати в журнал транзакції логічні записи redo і згодом їх застосовувати, використовуючи, по суті, відновлення redo (відновлення з повторним виконанням операцій). Звичайно, цей процес порушує кілька традиційних припущень про журналізації, наприклад, що операції redo – це завжди фізичні операції, які вже здійснилися, що операції r edo не можуть закінчуватися невдало і т.д. Проте залежно від програми такі збійні ситуації могли б не бути катастрофою, і їх можна було б ігнорувати, наприклад, цілком припустимі ситуації, коли в додатку відстеження рухомих засобів деякі окремі звіти про місцезнаходження не можуть бути записані в історичний індекс. Ясно, що цю ідею можна було б застосувати, але її деталі вимагають опрацювання, наприклад, що обіцяє і гарантує фіксація транзакції, як працюють контрольні точки і що вони гарантують і т.д.

6.2 B-дерева без журналізації

У деяких системах баз даних при створенні індексів використовуються спеціальні методи, що перешкоджають появі вмісту нового індексу в журналі транзакції. Замість цього журналізуются тільки зміни каталогу і виділення сторінок. Збій у процесі створення індексу призводить до повернення цих сторінок і підчистки інформації про новий індексі в каталозі. Створення індексу закінчується скиданням на диск всіх заново виділених і заповнених сторінок і наступними операціями резервного копіювання бази даних і навіть журналу транзакцій, що утримує інформацію про ці нові сторінках. Наступні користувача транзакції журналізуют свої зміни в новому індексі звичайним чином.

Цю ідею можна розширити таким чином. Якщо індекс є дійсно надлишковим, подібно до традиційного кешу, і якщо допустимо руйнування індексу протягом відновлення носія даних або системи, то всі операції над цим індексом можуть не журналізоваться, тобто журналізуется тільки розподіл пам’яті. Це включає і призначені для користувача транзакції, виконувані після завершення створення індексу. Відкат користувальницької транзакції управляється віртуальними журнальними записами, приєднаними до описувач транзакції в основній пам’яті, аналогічно віртуальним журнальним записів, які використовуються в інших методах управління транзакціями [G 04, GK 85]. Деталі цього методу в даний час не опубліковані, але для деяких програм цей метод здається цілком обіцяють, зокрема, для тимчасових кешей та індексів, що існують тільки в основній пам’яті.

6.3 Пакетні поновлення

Нарешті, можна групувати декілька операцій поновлення і транзакцій в одну транзакцію. Однак здається важливим відокремлювати семантику транзакцій від структури даних. Наприклад, як описувалося вище, багато невеликих користувацьких транзакцій можуть виробляти вставки в один буфер, залишаючи на подальшу системну транзакцію (або послідовність невеликих системних транзакцій) роботу з уливання цих вставок в основне B-дерево. Іншими словами, для досягнення роблять поліпшення продуктивності і масштабованості може не турбуватися чи не бути корисним модифікація або ослаблення кордонів і семантики користувача транзакцій.

7. Резюме і висновок


Таким чином, якщо погодитися з погіршенням продуктивності при обробці запитів на порядок, наприклад, за рахунок пошуку в кількох розділах, то продуктивність операцій оновлення і вставки можна підняти не менш ніж на два порядки, наприклад, шляхом перетворення операцій вставки в операції доповнення та перетворення випадкових поодиноких записів у великі послідовні записи в заново виділяється дисковий простір. Є і менш драматичні компроміси. Хоча в більшості програм виконується більше запитів, ніж операцій оновлення, і це призводить до організації бази даних, орієнтованої на оптимізацію запитів, деякі програми (наприклад, відстеження рухомих об’єктів) більше зайняті записом змін, ніж наданням відповідей на запити (наприклад, про поточну позиції об’єкта). Для таких програм вже є численні методи, які залишилося реалізувати постачальникам баз даних. Деякі з цих методів доступні навіть для користувачів баз даних, наприклад, введення штучного лідируючого стовпця ключа у видимій схемою бази даних і використання його для створення індексу і, можливо, для його підтримки при виконанні масових операцій [G 03b].

У цьому огляді ми намагалися перерахувати різноманітні можливі методи. Нові методи включають B-дерева, оптимізовані для запису, що розділяються B-дерева, в яких розділи використовуються для буферизації вставок або всіх модифікацій в манері диференціальних файлів, і B-дерева без журналізації. Однак наша інтуїтивна оцінка потребує підтвердження з використанням прототипування або навіть виробничої реалізації.

Очевидно наявність численних відкритих питань, включаючи питання про додаткові або поліпшених компроміси між ефективністю оновлень і запитів; порівняння ефективності описаних методів на основі відповідного тестового набору; адаптація описаних методів для інших індексних структур, таких як UB-дерева і R-дерева, а також матеріалізовані та індексні подання; інтеграція обробки запитів та операцій оновлення з операціями підтримки бази даних, такими як перевірка узгодженості, дефрагментація і оновлення статистики для оптимізації запитів. Може бути, цей огляд послужить стимулювання і структуризації таких досліджень.

8. Подяки


Тео Хардер (Theo Härder) і Берндхард Мітшанг (Bernhard Mitschang) читали попередні, неповні варіанти статті і зробили декілька дуже корисних зауважень.

9. Література


























































[A 96] Lars Arge: Efficient External-Memory Data Structures and Applications. University of Aarhus (Denmark), 1996. http://www.brics.dk/DS/96/3/BRICS-DS-96-3.pdf 
[ADR 03] Dave Anderson, Jim Dykes, Erik Riedel: More Than an Interface – SCSI vs. ATA. Conference on File and Storage Technology (FAST), March 2003. http://www.seagate.com/content/docs/pdf/whitepaper/ D2c_More_than_Interface_ATA_vs_SCSI_042003.pdf 
[AHV 02]   Lars Arge, Klaus Hinrichs, Jan Vahrenhold, Jeffrey Scott Vitter: . Algorithmica 33(1): 104-128 (2002). http://www.cs.duke.edu/~jsv/Papers/AHV99.bulk.pdf 
[G 03a] Goetz Graefe: Sorting and Indexing with Partitioned B-Trees. Conference on Innovative Data Systems Research, 2003. http://www-db.cs.wisc.edu/cidr/cidr2003/program/p1.pdf 
[G 03b] Goetz Graefe: Partitioned B-trees – a user”s guide. Datenbanksysteme f?r Business, Technologie und Web (BTW) 2003: 668-671. http://doesen0.informatik.uni-leipzig.de/proceedings/paper/IP11.pdf 
[G 04] Goetz Graefe: Write-Optimized B-Trees. VLDB Conference 2004: 672-683. http://www.vldb.org/conf/2004/RS18P2.PDF 
[GK 85] Dieter Gawlick, David Kinkade: Varieties of Concurrency Control in IMS/VS Fast Path. IEEE Data Eng. Bulletin 8(2): 3-10 (1985).
[GKK 01] Andreas G?rtner, Alfons Kemper, Donald Kossmann, Bernhard Zeller: Efficient Bulk Deletes in Relational Databases. IEEE ICDE 2001: 183-192. http://www.hpl.hp.com/techreports/tandem/TR-85.6.pdf 
[JNS 97] H. V. Jagadish, P. P. S. Narayan, S. Seshadri, S. Sudarshan, Rama Kanneganti: Incremental Organization for Data Recording and Warehousing. VLDB Conference 1997: 16-25 http://www.vldb.org/conf/1997/P016.PDF 
[LJB 95] Harry Leslie, Rohit Jain, Dave Birdsall, Hedieh Yaghmai: Efficient Search of Multi-Dimensional B-Trees. VLDB Conference 1995: 710-719. http://www.vldb.org/conf/1995/P710.PDF 
[MOP 00] Peter Muth, Patrick E. O”Neil, Achim Pick, Gerhard Weikum: The LHAM Log-Structured History Data Access Method. VLDB J. 8(3-4): 199-221 (2000). http://www.cs.umb.edu/~poneil/LHVLDBJ.pdf  
[OCG 96] Patrick E. O”Neil, Edward Cheng, Dieter Gawlick, Elizabeth J. O”Neil: The Log-Structured Merge-Tree (LSM-Tree). Acta Inf. 33(4): 351-385 (1996). http://www.cs.umb.edu/~poneil/lsmtree.ps 
[OD 89] John K. Ousterhout, Fred Douglis: Beating the I/O Bottleneck: A Case for Log-Structured File Systems. Operating Systems Review 23(1): 11-28 (1989). http://www.ugrad.cs.ubc.ca/~cs415/X/Info/papers-2003/ousterhout88beating.ps 
[PGK 88] David A. Patterson, Garth A. Gibson, Randy H. Katz: A Case for Redundant Arrays of Inexpensive Disks (RAID). ACM SIGMOD Conference 1988: 109-116. http://www.cs.cmu.edu/~garth/RAIDpaper/Patterson88.pdf 
[SL 76] Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267 (1976).
[U 84] David Ungar: Generation Scavenging: A Non-Disruptive High Performance Storage Reclamation Algorithm. Software Development Environments (SDE), ACM SIGPLAN Notices 19(5): 157-167 (1984).
[VSW 97] Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB Conference 1997: 406-415. http://www.vldb.org/conf/1997/P406.PDF 
[WKH 00] Till Westmann, Donald Kossmann, Sven Helmer, Guido Moerkotte: The Implementation and Performance of Compressed Databases. ACM SIGMOD Record 29(3): 55-67 (2000). http://www.dbis.ethz.ch/research/publications/sigrec00.pdf 

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*