Информация о работе
Подробнее о работе
ВЫПУСКАНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА на тему: «Теория индексов и её применение»
- 47 страниц
- 2025 год
- 0 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
Индексирование данных является одной из важнейших концепций в информатике и теории алгоритмов, позволяющей существенно ускорять операции поиска и выборки информации. Индекс в общем смысле – это дополнительная структура данных, ассоциированная с основным набором данных, которая организована таким образом, чтобы по заданному ключу быстро находить соответствующие элементы или записи. Классическим примером индекса служит указатель в конце книги: по ключевому слову можно мгновенно определить страницы, на которых оно упоминается. Аналогичный принцип применяется и в компьютерных системах: вместо последовательного просмотра всех данных (линейного поиска) используется индекс, позволяющий сразу перейти к нужному месту хранения данных.
Рост объёма данных в современных приложениях делает задачу эффективного поиска чрезвычайно актуальной. Без индексов многие операции базы данных или поискового движка работали бы неприемлемо медленно – фактически со скоростью, линейно зависящей от размера коллекции. Теория индексов изучает структуры данных, алгоритмы и методы, обеспечивающие быстрый доступ к данным – обычно за логарифмическое время O(log n) или близкое к постоянному O(1), вместо линейного O(n) на каждый запрос. Добиться этого ускорения позволяет использование специальных структур данных и алгоритмов. Конечно, выигрыш во времени достигается ценой дополнительной памяти под индекс и некоторых накладных расходов на его поддержание при обновлении данных. Таким образом, применение индексов представляет собой классический компромисс между временем и памятью.
Во введении обоснована актуальность темы исследования «Теория индексов и её применение», сформулированы цель и задачи работы. Целью данной работы является систематизация теоретических знаний об индексах и демонстрация их практического применения в различных областях компьютерных наук. Для достижения цели были поставлены следующие задачи: изучение фундаментальных структур данных, лежащих в основе индексов; анализ алгоритмов построения и использования индексов; обзор применения индексов в системах управления базами данных, поисковых системах и компиляторах; рассмотрение вопросов эффективности и оптимизации процессов индексирования.
Дипломная работа имеет следующую структуру. Глава 1 содержит теоретический обзор основных типов индексов: рассматриваются принципы организации B-деревьев, хеш-таблиц и инвертированных списков, приводятся свойства этих структур, оценки сложности операций и примеры алгоритмов. Глава 2 посвящена применению индексов в базах данных – описано, как реляционные СУБД используют B-деревья для индексации таблиц; рассмотрены типы индексов (первичные, вторичные, кластеризованные и др.), а также обсуждаются особенности хеш-индексов и современных структур типа LSM-деревьев, применяемых в NoSQL-системах. Глава 3 рассматривает индексы в информационно-поисковых системах: описывается построение инвертированного индексного файла для текстовой коллекции, приводятся алгоритмы обработки поисковых запросов на его основе, а также методы обновления и распределения индекса при большом объёме данных. Глава 4 посвящена индексам в компиляторах – в ней разбирается структура таблицы символов как примера индекса, используемого при трансляции программ, и даётся описание её реализации (чаще всего на базе хеш-таблицы) и использования на различных этапах компиляции.
В заключении подводятся итоги проделанной работы и формулируются основные выводы о значении теории индексов для эффективной обработки данных. Отмечается, что в работе использованы как классические подходы, так и современные научные достижения 2020–2025 годов в области индексирования. Приведён список использованных источников, отражающих как фундаментальные труды, так и новейшие исследования по теме.
ВВЕДЕНИЕ ……………………………………………………………
ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИНДЕКСОВ ИАЛГОРИТМИЧЕСКИХ СТРУКТУР ПОИСКА ……………………… 6
1.1 Понятие индекса в алгоритмах и структурах данных ……………… 6
1.2 B-деревья как структура индексирования …………………………… 10
1.3 Хеш-таблицы и хеширование ………………………………………… 16
1.4 Инвертированные индексы для текстового поиска ………………… 22
ГЛАВА 2. ПРИМЕНЕНИЕ ИНДЕКСОВ В БАЗАХ ДАННЫХ
2.1 Индексирование в реляционных СУБД (B-деревья, хеш-индексы) 28
2.2 Производительность запросов и выбор индексов ………………… 34
2.3 Современные подходы к индексированию (LSM-деревья и др.) … 38
ГЛАВА 3. ИНДЕКСЫ В ИНФОРМАЦИОННО-ПОИСКОВЫХ СИСТЕМАХ
3.1 Построение инвертированных индексов для текста ………………… 42
3.2 Алгоритмы поиска по индексу (булев поиск, ранжирование) …… 48
ГЛАВА 4. РЕАЛИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ В КОМПИЛЯТОРАХ
4.1 Таблицы символов как индексы идентификаторов ………………… 56
4.2 Реализация и алгоритмы работы таблицы символов ……………… 60
ЗАКЛЮЧЕНИЕ …………………………………………………………… 66
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ВКР систематизирует теорию индексов (B/B+-деревья, хеш-таблицы, инвертированные списки) и их применение в СУБД, поисковых системах и компиляторах, с анализом производительности и современных подходов (LSM).
Защита: 16.05.2025, Симферополь; оценка: Отлично.
1. Байер Р., МакКрейт Э. Организация больших упорядоченных индексов // Acta Informatica. – 1972. – №1. – С. 173–189. (Bayer R., McCreight E. Organization of large ordered indexes.)
2. Комер Д. Повсеместность B-деревьев // ACM Computing Surveys. – 1979. – Т.11, №2. – С. 121–137. (Comer D. The ubiquitous B-tree.)
3. Кнут Д. Искусство программирования. Т.3: Сортировка и поиск. – М.: Вильямс, 2002. – 832 с. (Knuth D. The Art of Computer Programming, Vol.3: Sorting and Searching.)
4. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Мир, 1983. – 440 с. (Aho A., Hopcroft J., Ullman J. Data Structures and Algorithms.)
5. Кормен Т. и др. Алгоритмы: построение и анализ. 3-е изд. – М.: Вильямс, 2013. – 1328 с. (Cormen T. et al. Introduction to Algorithms.)
6. Silberschatz A., Korth H.F., Sudarshan S. Database System Concepts. 6th ed. – New York: McGraw-Hill, 2011. – 1376 p.
7. Бейоза-Йейтс Р., Рибейро-Нето Б. Современные системы информационного поиска. – М.: Вильямс, 2011. – 576 с. (Baeza-Yates R., Ribeiro-Neto B. Modern Information Retrieval. – Addison-Wesley, 1999.)
8. Zobel J., Moffat A., Ramamohanarao K. Inverted files versus signature files for text indexing // ACM Trans. Database Syst. – 1998. – Vol.23, No.4. – P. 453–490.
9. Zobel J., Moffat A. Inverted files for text search engines // ACM Computing Surveys. – 2006. – Vol.38, No.2. – Article 6 (56 p.).
10. О’Нил П. и др. Алгоритм LSM-дерева: быстрая вставка в индексируемые последовательности // Acta Informatica. – 1996. – Т.33. – С. 385–406. (O’Neil P. et al. The log-structured merge-tree (LSM).)
11. Fagin R. et al. Extendible hashing – a fast access method for dynamic files // ACM Trans. Database Syst. – 1979. – Vol.4, No.3. – P. 315–344.
12. Лейс В. и др. Современные методы организации B-дерева // Proc. SIGMOD’25. – 2025. – (в печати). (Müller M., Benson L., Leis V. B-Trees Are Back: Engineering Fast Node Layouts.)
13. Bruch S. et al. Efficient inverted indexes for approximate retrieval over learned sparse representations // Proc. SIGIR’24. – 2024. – P. 2045–2054.
14. Краска Т. и др. Встроенные индексы, обученные данным // SIGMOD Record. – 2018. – Vol.47, No.2. – P. 22–29. (Kraska T. et al. The case for learned index structures.)
15. Fushimi S., Kitsuregawa M., Tanaka H. An overview of the system software of a parallel relational database machine: Delta // Proc. VLDB’86. – 1986. – P. 209–219.
16. Дин Дж., Гемават С. MapReduce: упрощенная обработка данных на кластерах // Comm. ACM. – 2008. – Т.51, №1. – С. 107–113. (Dean J., Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters.)
17. Chang F. et al. Bigtable: A Distributed Storage System for Structured Data // Proc. OSDI’2006. – 2006. – P. 205–218.
18. Брин С., Пейдж Л. Anatomy of a large-scale hypertextual Web search engine // Computer Networks. – 1998. – Vol.30, No.1–7. – P. 107–117.
19. Robertson S., Zaragoza H. The Probabilistic Relevance Framework: BM25 and Beyond // Foundations and Trends in Information Retrieval. – 2009. – Vol.3, No.4. – P. 333–389.
20. Porter M. An algorithm for suffix stripping // Program: Electronic Library and Information Systems. – 1980. – Vol.14, No.3. – P. 130–137.
21. Кросс-референс: GNU GLOBAL – инструмент индексирования исходного кода [Электронный ресурс]. – Режим доступа: https://www.gnu.org/software/global/ (дата обращения: 01.05.2025).
22. Nemariyi F.C., George A.C. Indexing techniques and structured queries for RDBMS // International Journal of Computer Science. – 2024. – Vol.12, No.3. – P. 45–53.
23. Maheshwari S.D. Inverted Index: The Backbone of Modern Search Engines [Электронный ресурс]. – Medium, 19.04.2025. – URL: https://satyadeepmaheshwari.medium.com/inverted-index (дата обращения: 01.05.2025).
24. GeeksforGeeks. Introduction of B-Tree [Электронный ресурс]. – 29.01.2025. – URL: https://www.geeksforgeeks.org/introduction-of-b-tree-2/ (дата обращения: 01.05.2025).
25. GeeksforGeeks. Inverted Index [Электронный ресурс]. – 11.03.2024. – URL: https://www.geeksforgeeks.org/inverted-index/ (дата обращения: 01.05.2025).
26. Musa Yusuf et al. Formalization of index building model for information retrieval systems // CyberLeninka. – 2024.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
