Упрощенное вычисление
Быстрый и грязный ответ - логарифмическая основа 100, округленная в большую сторону. То есть каждый узел в BTree имеет около 100 конечных узлов. В некоторых кругах это называется разветвлением.
1K строк: 2 уровня 1M строк: 3 уровня миллиард: 5 уровней триллион: 6 уровней
Эти числа работают для «средних» строк или индексов. Конечно, вы можете иметь экстремумы около 2 или 1000 для разветвления.
Точная глубина
Вы можете найти фактическую глубину из некоторой информационной_схемы:
Для Oracle * MySQL:
$where = "WHERE ( ( database_name = ? AND table_name = ? )
OR ( database_name = LOWER(?) AND table_name = LOWER(?) ) )";
$sql = "SELECT last_update,
n_rows,
'Data & PK' AS 'Type',
clustered_index_size * 16384 AS Bytes,
ROUND(clustered_index_size * 16384 / n_rows) AS 'Bytes/row',
clustered_index_size AS Pages,
ROUND(n_rows / clustered_index_size) AS 'Rows/page'
FROM mysql.innodb_table_stats
$where
UNION
SELECT last_update,
n_rows,
'Secondary Indexes' AS 'BTrees',
sum_of_other_index_sizes * 16384 AS Bytes,
ROUND(sum_of_other_index_sizes * 16384 / n_rows) AS 'Bytes/row',
sum_of_other_index_sizes AS Pages,
ROUND(n_rows / sum_of_other_index_sizes) AS 'Rows/page'
FROM mysql.innodb_table_stats
$where
AND sum_of_other_index_sizes > 0
";
Для Percona:
/* to enable stats:
percona < 5.5: set global userstat_running = 1;
5.5: set global userstat = 1; */
$sql = "SELECT i.INDEX_NAME as Index_Name,
IF(ROWS_READ IS NULL, 'Unused',
IF(ROWS_READ > 2e9, 'Overflow', ROWS_READ)) as Rows_Read
FROM (
SELECT DISTINCT TABLE_SCHEMA, TABLE_NAME, INDEX_NAME
FROM information_schema.STATISTICS
) i
LEFT JOIN information_schema.INDEX_STATISTICS s
ON i.TABLE_SCHEMA = s.TABLE_SCHEMA
AND i.TABLE_NAME = s.TABLE_NAME
AND i.INDEX_NAME = s.INDEX_NAME
WHERE i.TABLE_SCHEMA = ?
AND i.TABLE_NAME = ?
ORDER BY IF(i.INDEX_NAME = 'PRIMARY', 0, 1), i.INDEX_NAME";
(Те, которые дают больше, чем просто глубина.)
PRIMARY относится к данным BTree. Такие имена, как «n_diff_pfx03», относятся к 3-му уровню BTree; наибольшее такое число для таблицы указывает общую глубину.
Ширина строки
Что касается оценки ширины строки, см. ответ Билла. Вот еще один подход:
- Посмотрите размер каждого столбца (INT = 4 байта, используйте средние значения для VAR)
- Суммируйте их.
- Умножьте на 2 и 3 (чтобы учесть накладные расходы InnoDB)
- Разделить на 16 КБ, чтобы получить среднее число листьев узлов.
неконечных узлов, плюс индексный лист узлы сложнее, потому что вам нужно точно понимать, что представляет собой «строка» в таких узлах.
(Отсюда мое упрощение c «100 строк на узел».)
Но кого это волнует?
Вот еще одно упрощение, которое, кажется, работает довольно хорошо. Поскольку обращения к диску являются самым большим элементом производительности в запросах, вам необходимо «считать обращения к диску» как первый порядок оценки производительности запроса.
Но посмотрите на кэширование блоков в buffer_pool. Вероятность недавнего прикосновения к родительскому узлу в 100 раз выше, чем к дочернему узлу.
Таким образом, упрощение состоит в том, чтобы «предположить», что все неконечные узлы кэшируются и все конечные узлы необходимо извлекать с диска , Следовательно, глубина не так важна, как количество блоков конечных узлов. Это сбивает ваше «35% ускорение» - Уверенное 35% ускорение для CPU , но практически не ускорение для I / O . И ввод-вывод является важным компонентом.
Обратите внимание, что если вы выбираете последние 20 строк таблицы, которые хранятся в хронологическом порядке, они будут найдены в последних 1 (или, возможно, 2) блоках. Если они хранятся с помощью UUID, он с большей вероятностью будет рассказывать о 20 блоках - гораздо больше обращений к диску, а значит, гораздо медленнее.
Вторичные индексы
PRIMARY KEY кластеризован с данными. Это подразумевает, что при просмотре PK необходимо развернуть один BTree. Но вторичный индекс реализуется вторым BTree - просмотрите его, чтобы найти PK, затем разверните через PK. При «подсчете попаданий на диск» необходимо учитывать оба BTrees. И учтите случайность (например, для UUID) или нет (упорядоченную по дате).
Записывает
- Найти блок (возможно, кэшированный)
- Обновите его
- При необходимости разбейте блок на части
- Отметьте блок как «грязный» в buffer_pool
- В конце концов запишите его обратно на диск.
Шаг 1 может включать чтение ввода-вывода; шаг 5 может включать в себя запись ввода-вывода - но вы не дожидаетесь ее окончания sh.
обновления индекса
UNIQUE индексы должны быть проверено до окончания INSERT. Это включает потенциально кэшированный ввод-вывод для чтения.
Для неуникального индекса делается запись в «буфере изменений». (Это находится в buffer_pool.) В конце концов, это объединено с соответствующим блоком на диске. То есть не нужно ждать ввода-вывода, когда INSERTing строка (по крайней мере, не нужно ожидать обновления неуникальных индексов).
Следствие: UNIQUE индексы более дорогостоящие. Но есть ли необходимость в более чем 2 таких индексах (включая PK)?