By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,442 Members | 1,341 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,442 IT Pros & Developers. It's quick & easy.

Purpose of Doubly linked list in Btree index structures

Malathi
P: 31
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

✓ answered by 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?

Share this Question
Share on Google+
3 Replies


Rabbit
Expert Mod 10K+
P: 12,430
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
P: 31
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
Expert Mod 15k+
P: 31,768
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

Post your reply

Sign in to post your reply or Sign up for a free account.