Hi Markus,

I had a small doubt in the below article

http://use-the-index-luke.com/sql/anatomy/slow-indexes

Consider the search for “57” in Figure 1.3 again. There are obviously two matching entries in the index. At least two entries are the same, to be more precise: the next leaf node could have further entries for “57”. The database must read the next leaf node to see if there are any more matching entries. That means that an index lookup not only needs to perform the tree traversal, it also needs to follow the leaf node chain.

Only an index in the branch node will guide us to the correct leaf node wherein we can search for the required index from the internal indexes of the leaf node.If we traverse from one leaf node to other using the double linked list as mentioned above,wouldn't it break the b tree traversal wherein the leaf nodes are pointed to by the indexes from the branch node ?

Update :

Updating the question to make it clear.Not sure if it helps though as I couldn't get a pictorial representation to depict the query.

Below is the path that was followed for the lookup 57

branchnode(bn1) entry 83 -- > branchnode(bn2) entry 57 ----> leafnode(ln1) with multiple 57 entry's.

I believe the statement [it also needs to follow the leaf node chain] means follow from one leaf node(ln1) to the next leaf node(ln2) (using the list pointer) so as to search for entry's which match 57 in the leafnode(ln2).

So there can be a situation wherein we have to traverse from leafnonde(ln1) to leafnode(ln2) assuming ln2 has further entry's with value 57.Am i right in this assumption or did I get it wrong here itself ? Or does this mean searching for all the entry's with value 57 in ln1 itself.

The maximum entry in ln1 is defined by the entry in bn2 which got us there,so in our case as 57 entry from bn2 got us to ln1,the maximum entry value in ln1 can be at the max 57.So,even if there were multiple 57 entry's all of them should be in ln1 itself and they would not cross over to other leafnode(ln2) as that would disturb the order of entry's in bn2.

This might be a silly doubt,but I wanted to get this clarified so that its easy for me to understand further topics.

Thanks.