inserting into a table where an index column has sequential values

user_449693 0
Viewed 32

I have a table with a DATE column on it and I want to put an index on that column. But I happen to know values in that column are assigned sequentially. Mariadb uses B-trees by default, I think. Is this going to be a problem? Back in the old days this could create a "vine" in the index. and degrade performance. We are writing queries where date > (some date)

EDIT - a vine is a degenerate tree structure. Imagine this binary tree where 1 is the root. It's a valid binary tree but because the values were inserted sequentially, there's no 'tree' only a 'vine'; a single line of nodes.

1 -> 2 -> 3 -> 4 -> ...

mariadb indexing mysql
2 Answers

A B-tree is not a binary tree. B-trees are self-balancing (approximately). That is, all paths to leaf nodes tend to have the same length. Inserting a new entry, whether at the end or in the middle, will rebalance the tree automatically by the nature of the insertion algorithm. This includes splitting nonterminal nodes in the tree and shifting the tree to choose a new root node, so each child branch off the root has approximately equal subset of the tree.

If anything, inserting into a B-tree in sequential order helps to make the tree more compact and efficient. There's a good visualization of this advantage in this blog: https://www.percona.com/blog/2015/04/03/illustrating-primary-key-models-in-innodb-and-their-impact-on-disk-usage/

Bill_Karwin_208600

MySQL and MariaDB use B+Trees (see Wikipedia) for most indexes, including the PRIMARY KEY. A B+Tree allows efficient sequential scanning because there is a link from one block to the "next".

The tree is a bunch of blocks containing (typically) about 100 rows. (Row = data row or index row.)

When inserting, for example via AUTO_INCREMENT, into the "end" of the B+Tree, about 99 get added before a "block split" is required. This split turns the one block into to, and adds an entry in their parent block, which slowly creeps toward being full.

Note that about 1% of INSERTs lead to a split.

The tree is rebalanced during some of those block splits. The tree is kept balanced. (I don't know the details.) But it is infrequent enough that we should not worry about its cost.

Also, note that going from 1 million rows to 100 million rows adds only 1 level of BTree (from 3 to 4). A Binary Tree with 100M nodes would be about 27 levels deep.

user_17668310
Related