How are entries in index leaf node ordered?

Question

I am reading the book 'SQL performance explained' and when talking about indeces, it says that databases use doubly linked lists to connect index leaf nodes. Each node is stored in a database block and consists of different index entries.

It then says that the index order is maintained at two levels: one within each leaf node, and also within the different leaf nodes themselves (via the linked list), as you can see in the left side of the picture below.

My question is: I understand the advantages of using a doubly linked list for the blocks so that when inserting new blocks it's easier to maintain the order (it's a matter of moving around some pointers). However, within the block itself, if the order is maintained, how is that performant? Assuming than in a block there are a lot of entries, if one were to insert a new entry in the block, wouldn't that be really unperformant (because there is no data structure such as a doubly linked list).

Answer 1

The performance question you ask is a little more practical than the theory on how this works can answer. (I'm sure there's a Big O notation answer to generalize the performance but I don't know it off the top of my head.)

In practice, most database systems have different configuration options to decide when to split the block of the leaf level nodes. In Microsoft SQL Server for example, this is called Fill Factor. Fill Factor determines how full the leaf level block should be filled with data (ergo how much empty space is left available for future data inserts) on initial creation (or next rebuild of the index) to adjust how often a split operation should occur.

The previously linked article goes into the details, but in short this can be configured anywhere between 1% and 100% (in SQL Server 0% is a faux for 100%) meaning "leave the blocks 99% empty for future inserts" to "fill the block completely", and anywhere in between. This setting will affect performance in various ways, but inevitably a block split event will occur when a block is filled up and this somewhat of a heavier operation.

There is some compensation though, again in Microsoft SQL Server for example, where a small amount of Index Fragmentation occurs during this split events. This allows the split to occur more quickly at the trade-off that the physical ordering of the data may not exactly match the logical ordering of it in the B-Tree. This theoretically can affect performance during the final step of a SELECT query that uses that index, when a leaf node looks up the data page its data is stored in. Though this performance is very negligible in the real world and over time if enough index fragmentation occurs there are ways to fix it such as rebuilding or reorganizing the index.

In summary, yes there is a small amount of a performance hit when blocks need to split but modern database systems have different ways to control how often that occurs such as with the Fill Factor setting in MS SQL Server, and they lessen the performance hit by allowing fragmentation at the negligible tradeoff of querying against the index later on. They also offer ways to compensate for the tradeoffs of these optimizations by providing ways to fix the fragmentation via index rebuilding or reorganizing.

Answer 2

The actual data in a page is not necessarily in any particular order.

The logical order of data in any index 8k page is determined in the row offset array.

https://www.sqlservercentral.com/blogs/does-a-clustered-index-really-physically-store-the-rows-in-key-order

Answer 3

Consider the case of a single row lookup .. where key_column = some_value, a very common case. Having retrieved the block how does the DBMS find the specific key? Without some structure the only option is to scan all keys on that block, which may number in the thousands, an O(n) operation. If the keys in the block are ordered a binary search can be used which is O(log n). For 1,000 keys in the block a scan will, on average, touch 500 rows and a binary search 10. Much performanter.

Similarly with range scans, another frequent case. Having done 10 steps to find the first matching key all other matching keys must necessarily be adjacent since the keys are sorted. Without this structure the only option is to examine every row in the block.

You are correct about the additional work required during insert. It is an overhead. A designer of DBMSs must consider the whole workload her system is likely to see. A row is only ever inserted once; it will be read a great many times. On balance it is better to optimise for read performance over insert.

That said, insert optimisations are possible. One is to only store the index keys in sorted order together with a pointer to the remainder of the data elsewhere in the block. This is known as a slot array. These pointers can be small since they only have to reference within the block. During insert only these (key,pointer) pairs are moved around. The bulk of the data is not repositioned during insert. As the block must be in RAM to be altered all the slot array entries above where the new row is going to go can be shuffled across in a single, efficient operation.

There are storage formats which are optimised for write over read. The log structured merge tree is one. Even that sorts records in memory before they are persisted on disk so reads can be more efficient.