Purpose of Doubly linked list in Btree index structures

Malathi

Hi,

In SQL clustered tables (B tree), pages are linked in all levels by doubly linked list. Already the index is pointing to the corresponding pages then why we need the doubly linked list between pages? Any help is appreciated.

Thanks in Advance,
Malathi

Dec 20 '12 #1

Rabbit

This is a quote from wikipedia about double linked lists.

While adding or removing a node in a doubly linked list requires changing more links than the same operations on a singly linked list, the operations are simpler and potentially more efficient (for nodes other than first nodes) because there is no need to keep track of the previous node during traversal or no need to traverse the list to find the previous node, so that its link can be modified.

Dec 20 '12 #2

Malathi

Thanks for the reply. Please find the clustered index structure from the below link.
ms-help://MS.SQLCC.v10/MS.SQLSVR.v10.en/s10de_0evalplan/html/26b28045-c3c2-465a-b564-bf2189e93fdc.htm
Here we have index to find records, so why do we need linked list?

Dec 20 '12 #3

NeoPa

Although that question has already been answered fully, let's see if we can pad that out with something to help you understand it.

When going forwards through a list the single-linked list is adequate. When traversing a list in both directions, this is not the case. Going backwards through such a list requires finding the record again from scratch unless it is doubly-linked (or the calling code keeps its own track of where it's already been).

Does that make the difference clearer?

Dec 20 '12 #4