Индексирование базы данных: пример

Question

У меня скоро экзамен, и я хочу знать, как решить эти вопросы об индексировании:

1. База данных состоит из отношения R (A, B, C). А и В представляют собой целые числа [0,10 000] (по 4В каждый), а С представляет собой варкар (20) (20В) Отношение R состоит из 10 ^ 6 кортежей. Размер блока составляет 2048 B.

A) Сколько блоков мы должны прочитать (лучший и худший), если мы зададим этот запрос, если у нас есть индекс B + -дерева на B:

ВЫБРАТЬ C ОТ R, ГДЕ A = 100 и B = 10

B) Имеет ли смысл индексировать А? Если да, то какой тип индексов лучший?

Еще один похожий вопрос:

2. База данных состоит из отношения R (A, B, C). А и В представляют собой целые числа [0,10 000], а С представляет собой варчар (150). Отношение R состоит из 10 ^ 6 кортежей. Размер блока составляет 2048 B, а A, B - ключи.

A) Сколько блоков нам нужно прочитать в лучшем и худшем случаях, если мы зададим запрос "ВЫБЕРИТЕ C ОТ R, ГДЕ A = 4711 и:

• У нас нет индекса.
• У нас есть индекс B + -дерева на A и B.

b) Имеет ли смысл индексировать B отдельно и A отдельно вместо того, чтобы иметь один индекс для A и B. Какой тип индексов является лучшим?

EDIT

Вот что я сделал:

Вопрос 1 A)

Кортеж имеет размер = 20 + 4 + 4 = 28 B

2048/28 = 73 кортежа / блок округляется в меньшую сторону

10 ^ 6/73 = 13 699 блоков для целого отношения, округленные в сторону увеличения

Indexreadings : 4 * n + 4 (n + 1) <= 2048 B => n = 255 округляется в меньшую сторону

первый уровень дерева B + = 255 <10 ^ 6 Нет </p>

второй уровень дерева B + = 255 * 256 <10 ^ 6 Нет </p>

третий уровень дерева B + = 255 * 256 * 257> 10 ^ 6 Да, 10 ^ 6 кортежей могут поместиться в дерево B + высотой 3.

Datareadings : Если мы предположим, что A = 100 имеет вероятность 1/10001, а B = 10 имеет такую ​​же вероятность, то имеем:

1/10001 * 1/10001 * 10 ^ 6 с округлением = 1 кортеж

В худшем и лучшем случае: 1 кортеж = 1 блок

Тогда у нас 3 + 1 блокировка

Это правильно?

Я не знаю, как сделать Б) ..

И я действительно не знаю, как ответить на вопрос 2 .. Пожалуйста, помогите мне

Answer 1

Просто несколько заметок.Ваш лучший случай 1А кажется почти правильным (в некотором роде, но добавил: внизу), но я думаю, что ваш размер блока неверен.Только (значение) B и указатель / ссылка на нужный блок диска должны храниться в дереве индекса b +.Ни A, ни C вообще не должны быть в дереве b +.

И ваш худший случай действительно неверен.Нет требования, чтобы B был уникальным, и нет необходимости делать вероятность, когда речь идет о худшем случае.

Итак, представьте, что произойдет, если B = 10 во всех ваших кортежах.Затем вам нужно будет прочитать их все, чтобы найти значения, где A = 100.(Помните, что вас спрашивают о наилучшем / худшем, а не среднем).

Этот пример наихудшего случая также является вашей подсказкой для решения вопроса 1B.Индекс может быть полезен, если у вас так много значений с одинаковыми значениями B, что их нельзя разместить в нескольких блоках.(Вы можете сделать точную математику).

2A не кажется таким сложным.Если у нас нет индекса, то вам нужно прочитать 1 блок в лучшем случае и все блоки в худшем случае.(Предполагается, что A уникален. Это то, что A означает «ключ», верно?)

Но я немного запутался в этом последнем вопросе.Если A и B - это 2 разных (чужих ???) ключа, то объединенный индекс для них обоих кажется неправильным.

ps: Несколько лет назад я сделал это для университета, так что я могу бытьнеправильно, но я надеюсь, что я хотя бы дал вам кое-что подумать:}

Добавлено: -----------------

Моя заметка оВаши расчеты того, сколько записей вы можете иметь в одном узле, кажутся действительно неверными.Попробуйте вместо этого: (Все еще из памяти, извините за любые ошибки).

Запись в вашем дереве b +, содержит 2 значения B (min / max) и ссылку на блок диска для блока, содержащего значениямежду мин и макс.Таким образом, каждая запись составляет 12 байтов (при условии 4-байтовых ссылок на блоки), и таким образом вы можете хранить 2048/12 = 170 записей в каждом блоке.