Introduction to Indexes

Question

Post reply

Introduction to Indexes

Viewing 15 posts - 91 through 105 (of 124 total)

You must be logged in to reply to this topic. Login to reply

Gail Shaw SSC Guru Points: 1004494 More actions · Answer 1

tfifield (1/7/2011)

Are they a double linked list? I see from the diagrams that they link forward. Do they link backwards also?

Yes. If it's not in the diagram, it's just an omission due to simplification

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

tfifield SSCrazy Eights Points: 9655 More actions · Answer 2

tfifield

SSCrazy Eights

Points: 9655

January 7, 2011 at 4:07 pm

#1270964

Gail,

Thanks. I'm looking forward to the next articles..

Todd Fifield

Gail Shaw SSC Guru Points: 1004494 More actions · Answer 3

tfifield (1/7/2011)

Thanks. I'm looking forward to the next articles..

No need to look forward. The links at the bottom of this article will take you straight to them. These were originally published NoV 2009.

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

Jeff Moden SSC Guru Points: 1000539 More actions · Answer 4

Sorry I didn't comment on this series of articles before, Gail. They're absolutely awesome and should be required reading for everyone from SQL Neophyte to Ninja. Very well done. Thanks for taking the time to write this series.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.
"Change is inevitable... change for the better is not".

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)
Intro to Tally Tables and Functions

JacekO SSCertifiable Points: 6610 More actions · Answer 5

GLIC DBA (10/28/2009)

I didn't realize the working of a cluster index in SQL Server is different from that of a clustered index in Sybase. I erroneously thought that they are the same since at one time the two were the same product. The following is from the Sybase ref man. "With a clustered index, Adaptive Server sorts rows on an ongoing basis so that their physical order is the same as their logical (indexed) order. The bottom or leaf level of a clustered index contains the actual data pages of the table." This is just another difference between the two RDBMSs which I'll have to remember. Thanks again for following up on yesterday's question.

I think there are two issues of the logical vs physical order. One is about order of the data pages and the other is about the order of the rows of data within the page. I think when Gail mentioned the logical order she ment the order of data pages and their storage on the disk. That excerpt from Sybase manual is talking about the order of the data rows within a page.

If I am not mistaken SQL Server clustered index rows are sorted physically within the IN_ROW_DATA data pages.

---------------------------------------------
[font="Verdana"]Nothing is impossible.
It is just a matter of time and money.[/font]

Gail Shaw SSC Guru Points: 1004494 More actions · Answer 6

JacekO (1/26/2011)

I think there are two issues of the logical vs physical order. One is about order of the data pages and the other is about the order of the rows of data within the page. I think when Gail mentioned the logical order she ment the order of data pages and their storage on the disk.

I meant both. The pages may not be physically ordered on disk, the rows may not be physically ordered on a page. Dunno about Sybase (that manual may be correct), but in SQL pages have what's called the slot array at the end of the page that indicate the logical order of the rows. The physical order depends on insert order, deletes, other stuff.

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

JacekO SSCertifiable Points: 6610 More actions · Answer 7

JacekO

SSCertifiable

Points: 6610

January 26, 2011 at 1:01 pm

#1278738

Thanks for the clarification. That slot array. Is this a fairly new thing or it was like this for a while ( I mean SQL Server versions)?

---------------------------------------------
[font="Verdana"]Nothing is impossible.
It is just a matter of time and money.[/font]

JacekO SSCertifiable Points: 6610 More actions · Answer 8

JacekO

SSCertifiable

Points: 6610

January 26, 2011 at 1:02 pm

#1278739

Another question about that slot array. I understand this is only on the clustered index pages. Correct?

---------------------------------------------
[font="Verdana"]Nothing is impossible.
It is just a matter of time and money.[/font]

Gail Shaw SSC Guru Points: 1004494 More actions · Answer 9

It's been like that since at least the storage engine rewrite before last. That's SQL 7. Maybe before, I have no familiarity with SQL 6.5

As for the slot array on nonclustered index leaf page, consider that homework 🙂 😉

DBCC IND(<Database_ID>, <Object_ID>, <Index_ID>)

to find the pages in the index. Look for one with index level = 0, that will be a leaf page

DBCC TRACEON(3604)



DBCC PAGE (<Database ID>,<File ID>,<Page Number>,1)

DBCC TRACEOFF(3604)

That will dump the page with the portions of it interpreted for you. Look at the end and see if you see the OFFSET TABLE (what the slot array is called in the DBCC Page output

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

JacekO SSCertifiable Points: 6610 More actions · Answer 10

JacekO

SSCertifiable

Points: 6610

January 26, 2011 at 1:36 pm

#1278760

Wow,

Now instead of giving me a fish you are trying to send me out to sea with a net... 😉

Thanks.

Now I have to check out and head home before the snow covers the roads...

---------------------------------------------
[font="Verdana"]Nothing is impossible.
It is just a matter of time and money.[/font]

Gail Shaw SSC Guru Points: 1004494 More actions · Answer 11

JacekO (1/26/2011)

Wow,

Now instead of giving me a fish you are trying to send me out to sea with a net... 😉

And instructions. 😀

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

vj2173 Grasshopper Points: 14 More actions · Answer 12

I'm an extreme Newbie and I'm trying to clarify my own understanding of indexes. You mentioned that,

"The non-leaf levels of the index contain one row per page of the level below, referencing the lowest index key value on each page."

Correct me if I'm wrong, but the root page contains the actual values from the index column.

ID

1

2

3

4

This can span out if the index column has 10,000 records?

ID

1

2

3

...

.. 10,000

those values are divided up within the Intermediate Level

ID (Intermediate1)

1

2

3

4

ID (Intermediate2)

5

6

7

8

this spread across to accomodate the number of rows in the index column

ID (IntermediateN?)

..

record 10,000

this is then populated in the Leaf level? Is this presumption, correct?

Thanks,

Gail Shaw SSC Guru Points: 1004494 More actions · Answer 13

I'm not sure I understand you. I suggest you read parts 2 and 3 where I have diagrams of the index structure.

The only level of the index that has all key values is the leaf level.

Gail Shaw
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)
SQL In The Wild: Discussions on DB performance with occasional diversions into recoverability

We walk in the dark places no others will enter
We stand on the bridge and no one may pass

hallidayd SSCrazy Points: 2490 More actions · Answer 14

hallidayd

SSCrazy

Points: 2490

January 28, 2011 at 9:22 am

#1279767

Gail is right - the root and intermediate index levels store only key range boundary values since all they are required for are routing to the relevant next page. There is no reason to store every value - that would be inefficient.

vj2173 Grasshopper Points: 14 More actions · Answer 15

Thank you for the response. I read the 2nd article and I notice that in your diagram you have

1

4

13

for the Intermediate Level. And like your last response, the leaf level contains all of the data for the particular row.

1 Mr. Adam Taylor

2. Mr. Richard Wright

3. Miss Helen Smith

Which I follow. My confusion is with the root and intermediate pages.

From your diagram, am I to assume that the root page contain the indexed column and all of the values from the index column. From

1 to 137?

Secondly, the Intermediate pages (level) hold segments of those values from the indexed column?