Потерпи меня, это займет некоторое время: -).
Представьте себе простую адресную книгу, в которую вы просто добавляете записи в конце, когда приходят новые друзья или коллеги (следующая запись будет в 5):
1. Bob Smith, 7 Station St, Wotahole, NJ
2. Greg Jones, 3 Railway Pde, Boot Hill, KA
3. Allan Brown, 27 Carriage Court, Washington, DC (home)
4. Allan Brown, 1066 Hastings Street, Washington, DC (work)
5.
Теперь вам нужно найти чей-то адрес. Нет проблем, я слышал, вы говорите, просто отсканируйте список в поисках имени, затем прочитайте адрес.
Теперь, что если вы настолько потрясающе популярны, что у вас есть 1024 друга, таких как я (я такой придурок, я делю друзей только на две степени - у меня на самом деле 2024, но 1000 из них содержатся в подвешенном состоянии Я могу собрать еще 24 вместе: -).
Чтобы найти конкретного друга, вам нужно отсканировать в среднем 512 записей (половина из которых используется). Это довольно утомительно. В худшем случае сканируются все 1024 из них, чтобы найти последнего добавленного вами человека.
Теперь давайте добавим этот индекс. Каждый раз, когда вы добавляете нового друга / коллегу (или удаляете их, если они доставляют вам слишком много хлопот), вы обновляете этот индекс, в котором хранится только имя в отсортированном порядке вместе с номером строки полной записи (индексные страницы в вашем адресе книги волшебные и автоматически сортируют все что в них написано).
Индекс для нашего мини-списка выше:
1. Allan Brown, 3
2. Allan Brown, 4
3. Greg Jones, 2
4. Bob Smith, 1
Имена и номера строк занимают меньше места, чем полные записи, но наиболее важный аспект заключается в следующем.
Чтобы найти запись, вам нужно отсканировать, в худшем случае, 10 записей (журнал 2 1024). Сначала вы проверяете индекс 512. Если имя, которое вы ищете, больше этого, вам нужно только взглянуть на записи 513-1024. Если оно меньше, вас сейчас интересуют только записи 1-511. В любом случае вы сразу же сократили свое пространство поиска наполовину.
При использовании оригинального метода вы можете отказаться только от проверенного вами, поскольку у вас нет информации о заказе.
Таким образом, размер пространства поиска выглядит следующим образом (я фактически использовал степени два для индексированного метода, но он немного лучше):
+-----------+----------------+------------+
| Iteration | Indexed method | Old method |
+-----------+----------------+------------+
| 0 | 1024 | 1024 |
| 1 | 512 | 1023 |
| 2 | 256 | 1022 |
| 3 | 128 | 1021 |
| 4 | 64 | 1020 |
| 5 | 32 | 1019 |
| 6 | 16 | 1018 |
| 7 | 8 | 1017 |
| 8 | 4 | 1016 |
| 9 | 2 | 1015 |
| 10 | 1 | 1014 |
+-----------+----------------+------------+
Как только вы нашли индекс, извлеките из него номер строки и, поскольку вы знаете, что у вас есть 16 записей на странице, номер записи 275 (например) находится на стр. 18, строка 4. Вы можете идти прямо. там без дальнейших поисков.
Итак, потратив немного больше места для хранения и потратив некоторое время на поддержание индекса, вы значительно повысили скорость поиска. И это то же самое делают индексы в базах данных.