9

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.

1
  • 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... Jan 2, 2012 at 10:56

1 Answer 1

4

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
8
  • 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, 2011 at 21:08
  • 1
    @someName - The table pages are the leaf nodes of the clustered index implicitly created by the PRIMARY KEY. Apr 29, 2011 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, 2011 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. Apr 29, 2011 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, 2011 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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