Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Consider a B-tree index on a value that will always increase monotonically, e.g. a column of type IDENTITY. With a conventional B-tree implementation, whenever a node is full, it will be split 50%/50% and we end up with a B-tree in which (almost) all nodes will be only 50% full.

I know that Oracle discovers when a value is ever-increasing and in these cases Oracle performs a 90%/10% split instead. That way, (almost) all nodes will be 90% full and a far better page utilization is obtained for these, quite common, cases.

I have not been able to find documentation for a similar feature in SQL Server. However, I have performed two experiments in which I inserted N random integers, and N consecutive integers in an index, respectively. The former case used far more pages the latter.

Does SQL Server provide a similar functionality? If so: can you point me to some documentation on this feature?

UPDATE: It seems, by the experiments provided below, that leaf nodes are kept un-splitted and internal nodes are split 50%/50%. That makes B-trees on increasing keys more compact than on random keys. However, the 90%/10%-approach by Oracle is even better, and I still look for some official documentation that can verify the behavior seen in experiments.

share|improve this question

migrated from stackoverflow.com Dec 30 '11 at 16:51

This question came from our site for professional and enthusiast programmers.

    
It seems an acceptable answer to this question would probably be some documentation that lists all the various types of page split that can occur and when they can occur. I'm not currently aware of such a resource but maybe someone here is... –  Martin Smith Jan 2 '12 at 10:56

1 Answer 1

If it is adding a row at the end of the index it will just allocate a new page for the row rather than split the current end page. Experimental evidence for this is below (uses the %%physloc%% function which requires SQL Server 2008). See also the discussion here.

CREATE TABLE T
(
id int identity(1,1) PRIMARY KEY,
filler char(1000)
)
GO

INSERT INTO T
DEFAULT VALUES
GO 7

GO
SELECT sys.fn_PhysLocFormatter(%%physloc%%)
FROM T

GO

INSERT INTO T
DEFAULT VALUES

GO

SELECT sys.fn_PhysLocFormatter(%%physloc%%)
FROM T
GO

DROP TABLE T

Returns (Your results will vary)

(1:173:0) /*File:Page:Slot*/
(1:173:1)
(1:173:2)
(1:173:3)
(1:173:4)
(1:173:5)
(1:173:6)
(1:110:0) /*Final insert is on a new page*/

This does only appear to apply to leaf nodes though. This can be seen by running the below and adjusting the TOP value. For me 622/623 was the cut off point between requiring one and two first level pages (might vary if you have snapshot isolation enabled?). It does split the page in a balanced manner leading to wasted space at this level.

USE tempdb;

CREATE TABLE T2
(
id int identity(1,1) PRIMARY KEY CLUSTERED,
filler char(8000)
)

INSERT INTO T2(filler)
SELECT TOP 622 'A'
FROM master..spt_values v1,  master..spt_values v2

DECLARE @index_info  TABLE
(PageFID  VARCHAR(10), 
  PagePID VARCHAR(10),   
  IAMFID   tinyint, 
  IAMPID  int, 
  ObjectID  int,
  IndexID  tinyint,
  PartitionNumber tinyint,
  PartitionID bigint,
  iam_chain_type  varchar(30),    
  PageType  tinyint, 
  IndexLevel  tinyint,
  NextPageFID  tinyint,
  NextPagePID  int,
  PrevPageFID  tinyint,
  PrevPagePID int, 
  Primary Key (PageFID, PagePID));

INSERT INTO @index_info 
    EXEC ('DBCC IND ( tempdb, T2, -1)'  ); 

DECLARE @DynSQL nvarchar(max) = 'DBCC TRACEON (3604);'
SELECT @DynSQL = @DynSQL + '
DBCC PAGE(tempdb, ' + PageFID + ', ' + PagePID + ', 3); '
FROM @index_info     
WHERE IndexLevel = 1

SET @DynSQL = @DynSQL + '
DBCC TRACEOFF(3604); '

EXEC(@DynSQL)


DROP TABLE T2
share|improve this answer
    
Thanks. But notice, that I'm asking for the behavior of the B-tree index nodes - not the table pages. Interesting read though. :-) –  someName Apr 29 '11 at 21:08
1  
@someName - The table pages are the leaf nodes of the clustered index implicitly created by the PRIMARY KEY. –  Martin Smith Apr 29 '11 at 21:11
    
Ah, I see. That insertion strategy is certainly space efficient. But I fail to see how this fits into the B-tree structure: With the "add-to-new-page-instead-of-splitting" strategy we end up with a long linked list, and not a B-tree. How are specific values retrieved using only a logarithmic number of lookups (I/O's) in this linked list? –  someName Apr 29 '11 at 21:32
    
This is only the leaf node level. As soon as the leaf node level has more than 1 page there will be another level above. You can use DBCC IND and sys.dm_db_index_physical_stats to see info on these. –  Martin Smith Apr 29 '11 at 21:34
    
But whenever one of the non-leaf nodes are full i will be split. And that split, I guess, is 50%/50%? Or 90%/10% as Oracle does it? –  someName Apr 29 '11 at 21:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.