472,779 Members | 1,751 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,779 software developers and data experts.

Purpose of Doubly linked list in Btree index structures

Malathi
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?

3 2897
Rabbit
12,516 Expert Mod 8TB
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
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
32,534 Expert Mod 16PB
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

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

Similar topics

5
by: Daniel | last post by:
I need to reverse the doubly linked list with dummy node. I think the solution is to exchange each node pointers' next and previous address. But what's wrong in my function? Thanks void...
4
by: dssuresh6 | last post by:
Whether browsing forward or backward can be done using a singly linked list. Is there any specific case where a doubly linked list is needed? For people who say that singly linked list allows...
0
by: drewy2k12 | last post by:
Heres the story, I have to create a doubly linked list for class, and i have no clue on how to do it, i can barely create a single linked list. It has to have both a head and a tail pointer, and...
6
by: Joe Estock | last post by:
I'm attempting to sort a doubly linked list at the time that an item is added. When I add the items in increasing order everything works correctly, however when I add them in reverse order the...
2
by: murali | last post by:
Hi, I want to insert a node in an sorted doubly linked list of integers in ascending order. The list should not have duplicate nodes. I need an algorithm (assuming an object oriented language) ...
2
by: zoro | last post by:
hello: i'm not sure what the operations that would be affected if we didn't maintain a tail pointer in doubly linked list? so why is it important? your help is appreciated thank you
5
by: adam.kleinbaum | last post by:
Hi there, I'm a novice C programmer working with a series of large (30,000 x 30,000) sparse matrices on a Linux system using the GCC compiler. To represent and store these matrices, I'd like to...
4
kim6987
by: kim6987 | last post by:
can you please spend a little time evaluating this code. I can not run it successfully thanks :) #include<stdio.h> #include<conio.h> #include<stdlib.h> #define SIZE 10 typedef struct dlist
1
by: Mahesh | last post by:
Hi Coders, I was asked to write a program to interchange numbers using doubly linked list @ Amazon. Here is the details with Code that i wrote. i/p: 1 2 3 4 5 6 7 8 .....n,n-1. o/p: 2 1 4...
4
by: arnuld | last post by:
This program follows from the section 6.5 of K&R2 where authors created a doubly-linked list using a binary-tree based approach. The only thing I have rewritten myself is the getword function. I am...
0
by: Rina0 | last post by:
Cybersecurity engineering is a specialized field that focuses on the design, development, and implementation of systems, processes, and technologies that protect against cyber threats and...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 2 August 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central...
0
linyimin
by: linyimin | last post by:
Spring Startup Analyzer generates an interactive Spring application startup report that lets you understand what contributes to the application startup time and helps to optimize it. Support for...
0
by: kcodez | last post by:
As a H5 game development enthusiast, I recently wrote a very interesting little game - Toy Claw ((http://claw.kjeek.com/))。Here I will summarize and share the development experience here, and hope it...
0
by: Taofi | last post by:
I try to insert a new record but the error message says the number of query names and destination fields are not the same This are my field names ID, Budgeted, Actual, Status and Differences ...
0
by: Rina0 | last post by:
I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in...
5
by: DJRhino | last post by:
Private Sub CboDrawingID_BeforeUpdate(Cancel As Integer) If = 310029923 Or 310030138 Or 310030152 Or 310030346 Or 310030348 Or _ 310030356 Or 310030359 Or 310030362 Or...
0
by: lllomh | last post by:
Define the method first this.state = { buttonBackgroundColor: 'green', isBlinking: false, // A new status is added to identify whether the button is blinking or not } autoStart=()=>{
0
by: lllomh | last post by:
How does React native implement an English player?

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.