Індекси на основі 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] HV Jagadish, PPS 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>

*

*