Does the index in InnoDB and MyISAM keep amount of child nodes in B-trees?

Question

Does the index in InnoDB and MyISAM keep amount of child nodes in B-trees ?

If I have an b-tree index on (field1, field2) and we are dealing with MyISAM (to avoid issues with transactions, locking, etc), why not to store amount of child nodes on transition from one node into the child one in b-tree index ?

Here is a real-case sample:

Environment: MariaDB 10.6.7 Table Engine: tested on both InnoDB and MyISAM

I have a table with some fields, there are about 7 million rows. Now, I'm adding two indexes:

ALTER TABLE `table` ADD KEY `testKey1` (`country`);
ALTER TABLE `table` ADD KEY `testKey2` (`country`, `saleTimestamp`);

Then, I run a query:

SELECT COUNT(*) FROM `table` WHERE `country` = 'us';
+----------+
| COUNT(*) |
+----------+
|  5411930 |
+----------+
1 row in set (1.569 sec)

Explain shows what it uses index testKey2, which makes sense for me.

Question: how come that index doesn't have number of children ? So to find how many records we have to scan a lot of records.

I was just expecting that the index (country) would keep amount of child records (like in a tree, the amount of child nodes in some node), so if I ask how many records under the specific country, the MariaDB would simply get this information from the index.

Am I missing something ?

Thanks for helping

Answer 1

The B-Trees in MyISAM and InnoDB are radically different.

MyISAM -- 1KB B-Tree blocks for indexes only.

InnoDB -- 16KB B+Tree blocks for indexes and data. They are essentially identical, in that the "data" uses the PRIMARY KEY for indexing and ordering.

If you push me, I can talk further about MyISAM, but you really should avoid it.

Percona and Oracle have different ways to look at the stats. And things may have changed over the versions. See if any of these work for you:

Percona:

    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

Oracle:

$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";

also:

    SELECT  index_name,
                last_update,
                stat_name,
                stat_value
        FROM mysql.innodb_index_stats
        WHERE ( database_name = ?
            AND table_name = ? )
          OR    database_name = LOWER(?)
            AND table_name = LOWER(?)

Answer 2

As for your "questions":

Question: how come that index doesn't have number of children ?

For the simple reason that it would cost far too much to maintain the value.

COUNT(*) (without a WHERE) is sitting in the .MYI file for MyISAM, but cannot be dead-reckoned for InnoDB, so is unavailable. The reason: MVCC could have 'tentative' rows sitting around waiting for COMMIT.

Either of these

INDEX(`country`);
INDEX(`country`, `saleTimestamp`);

Should be as efficient as you can get for

SELECT COUNT(*) FROM `table` WHERE `country` = 'us';

Even MyISAM does not bother to keep the count. Again, it is because it is too much work. (Or perhaps because it is of so little use that it did not make the cut for "what is worth implementing".)

Of those two indexes, I recommend dropping the former, since the latter can handle virtually any query that the former is useful for, albeit slightly slower.