Проще говоря, индекс — это оптимизированная структура данных, которая позволяет более эффективно искать нашу исходную структуру.
В качестве общего примера, представьте себе Книга у вас есть. У вас есть основная структура, которая являетсясодержание книги. Но у вас также обычно есть две дополнительные структуры: оглавление и указатель в конце.
Оглавление — это структура, которая помогает нам быстро находить главы и разделы по названию, поэтому мы говорим, что книга проиндексирована по заголовкам глав и разделов.
Индекс помогает нам найти страницы по определенным словам. Так что книга тоже проиндексирована словами.
Использование любого из этих индексов позволит нам быстрее находить то, что нам нужно, так как без них нам пришлось бы сканировать всю книгу, пока мы не найдем то, что хотим.
Индексы помогают нам быстро находить данные, но, как видно из аналогии, они также добавляют дополнительную стоимость пространства (памяти) и стоимость записи, поскольку им необходимо поддерживать дополнительную обновленную структуру. Обращая внимание, мы также видим, что создание новой записи в индексе должно быть упорядочено, поэтому оно не может быть простой вставкой в конце индекса, но оно должно быть в правильной позиции.
Идея одинакова для БД или для поисковой системы. У нас есть основная структура данных (это таблицы и столбцы нашей модели в случае БД и наше текстовое содержимое в случае поисковых систем). И если мы создаем индекс, мы создаем другую структуру, которая позволит быстро искать основную структуру.
Сейчас мы сделаем небольшой пример на Java о том, как это будет работать для полнотекстового поиска, который индексирует по словам книги. Мы начинаем мы книгу и класс страницы
public class Book {
private List<Page> pages = new ArrayList<>();
public List<Page> getPages() {
return pages;
}
public void addPage(Page page) {
this.pages.add(page);
}
}
public class Page {
String content;
int number;
public Page(String content,int number){
this.content = content;
this.number = number;
}
public String getContent() {
return content;
}
public int getNumber() {
return number;
}
}public class Book {
private List<Page> pages = new ArrayList<>();
public List<Page> getPages() {
return pages;
}
public void addPage(Page page) {
this.pages.add(page);
}
}
public class Page {
String content;
int number;
public Page(String content,int number){
this.content = content;
this.number = number;
}
public String getContent() {
return content;
}
public int getNumber() {
return number;
}
}
Итак, давайте сделаем тестовый пример для книги на 10000 страниц (я знаю, что это большая фальшивая книга), а затем попробуем найти там слово:
Мы создаем искатель
public class NonIndexBookFinder implements BookFinder {
private Book book;
public NonIndexBookFinder(Book book){
this.book = book;
}
@Override
public Page findPage(String word) {
for(Page page : book.getPages()){
if(page.getContent().contains(word)){
return page;
}
}
return null;
}
}
Нет, мы создадим IndexFinder на основе Hash Map.
public class IndexBookFinder implements BookFinder {
private Map<String, Page> index = new HashMap<>();
public IndexBookFinder(Book book, String[] wordsToIndex) {
for (Page page : book.getPages()) {
for (String word : wordsToIndex) {
if (page.getContent().contains(word)) {
index.put(word, page);
}
}
}
}
@Override
public Page findPage(String word) {
return index.get(word);
}
}
Мы видим, что стоимость в Построение индекса сейчас. но поиск является операцией O (1).
Создание нашего кода тестирования
public class NoIndexBookTest {
public static void main(String[] args) {
final Book book = new Book();
for(int i=0;i<10000;i++){
Page page = new Page(createContentBasedOnIndex(i), i);
book.addPage(page);
}
final BookFinder finder = new NonIndexBookFinder(book);
timedFind(new Runnable() {
@Override
public void run() {
Page page = finder.findPage("tolook");
System.out.println("PAGE: "+page.getNumber());
}
});
final BookFinder finder2 = new IndexBookFinder(book,new String[]{"tolook"});
timedFind(new Runnable() {
@Override
public void run() {
Page page = finder2.findPage("tolook");
System.out.println("PAGE: "+page.getNumber());
}
});
}
private static String createContentBasedOnIndex(int pageNo) {
StringBuilder string = new StringBuilder();
for(int i=0;i<5000;i++){
string.append(" palabra ");
if(pageNo==9900 && i==4000){
string.append("tolook");
}
}
return string.toString();
}
private static void timedFind(Runnable runnable){
long init = System.currentTimeMillis();
runnable.run();
long end = System.currentTimeMillis();
System.out.println(end-init);
}
}
И выполняя мы получаем:
СТРАНИЦА: 9900
268
СТРАНИЦА: 9900
0
Как мы видим, индексированная версия выполняет поиск менее чем за 1 миллисекунду по сравнению с 270 миллисекундами, которые занимает первая.
Это очень простая реализация индекса на основе хэш-карт, но это идея. Конечно, ему не хватает почти всей функциональности, но идея состоит в том, чтобы простоАльтернативная структура используется для более быстрого поиска в основных данных.
Обычно реализации базы данных используют B-Tree для реализации своих индексов вместо Hashmap, как здесь используется. Определение B-дерева можно найти в Википедии здесь http://en.wikipedia.org/wiki/B-tree »> B-Tree. Суть в том, что они позволяют осуществлять поиск, вставку, удаление в логарифмическом времени. И они позволяют эффективный поиск по диапазонам, прямой, отсортированный и т. Д.
Я постараюсь
следуйте этому посту с немного более реалистичным примером индекса на основе B Tree.