Shocked. (A Halloween Horror story.)

Question

Shocked. (A Halloween Horror story.)

ben.brugman

SSChampion

Points: 13369
More actions
October 30, 2015 at 5:33 am

#301818

A Halloween Horror story.
As a fan of B - tree's (See: Wikipedia B tree)
I am also a fan of Clustered tables.
The B - tree meets the standard requirement:
"a B-tree minimizes waste by making sure the nodes are at least half full." (Except the root node).
So I asumed this to be true for Clustered tables as wel.
The Horror that I noticed that this is a wrong assumption from my side.
Can anybody explain to me why this B-tree requirement is not implemented as a requirement for clustered tables ?
Or do I misunderstand something ?
Ben
How this Horror creaped up onto me (still giving me the shivers):
Building a worse case scenario for Heap tables.
(100 rows, 90 forwarderd rows and an Avg. Page Density of 5.6%. And 191 logical reads for a full table scan).
I noticed that a clustered table with the same scenario was not doing a whole lot better.
So I was rather shocked that a worse scenario for heap tables, did also produce a Horror scenario for Clustered tables.
(Ok it's halloween, but still).

Viewing 3 posts - 1 through 2 (of 2 total)

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

Jeff Moden SSC Guru Points: 1004339 More actions · Answer 1

To be honest, I'd say the quote about "half full" is incorrect, at least about the implementation for Microsoft's interpretation of the Rushmore Engine (the basis of SQL Server).

--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)

ben.brugman SSChampion Points: 13369 More actions · Answer 2

Jeff Moden (10/31/2015)
To be honest, I'd say the quote about "half full" is incorrect, at least about the implementation for Microsoft's interpretation of the Rushmore Engine (the basis of SQL Server).

My assumptions is based on Knuth's description of B-tree's.

(The art of computer progamming volume 3).

To keep a Tree fairly balanced, nodes where the fill is less then 50 percent should be reorganised with their neighbours. So when a node goes below 50 percent some 'info' from the neighbour should be moved. Or when the neighbour does not have enough info then the two should be combined to one node. This is what keeps the B-tree fairly balanced.

So Knuth states : 2. Every node (except root) has at least m/2 children.

There sometimes discussion how the leaves should behave. But to keep the B-tree balanced I always interpreted Knuth rules to imply that rule 2 applies in a similar way to the leave nodes.

Ben

According to Knuth's definition, a B-tree of order m is a tree which satisfies the following properties:

1. Every node has at most m children.

2. Every non-leaf node (except root) has at least ?m/2? children.

3. The root has at least two children if it is not a leaf node.

4. A non-leaf node with k children contains k-1 keys.

5. All leaves appear in the same level

Remark:

For leaves nodes there is no mimimum fill requirement.

A non-leaf node must contain at least [m/2] children and [m/2] -1 keys. The actual fill is then near to 50 percent but still below 50 percent. So in normal speach I call this half full, but this is not exact, it is a very little less.