问Server中单调递增值的B树节点分割策略
EN

Database Administration用户

提问于 2011-04-29 12:43:38

回答 1查看 1.4K关注 0票数 9

考虑一个值的B树索引，它总是单调地增加，例如一个类型标识的列。对于传统的B树实现，每当节点已满时，它将被分割为50%/50%，我们最终会得到一个B树，其中(几乎)所有节点都将只满50%。

我知道Oracle会发现值不断增加，而在这些情况下，Oracle执行90%/10%的拆分。这样，(几乎)所有节点都将满90%，对于这些非常常见的情况，可以获得更好的页面利用率。

我无法在Server中找到类似特性的文档。但是，我做了两个实验，分别在索引中插入了N个随机整数和N个连续整数。前者使用的页面要多得多，后者则要多得多。

Server是否提供了类似的功能？如果是这样的话:你能告诉我一些关于这个特性的文档吗？

更新:根据下面提供的实验，叶节点保持不分裂，内部节点被分割50%/50%。这使得增加键的B树比随机键更紧凑.然而，Oracle的90%/10%的方法甚至更好，我仍然寻找一些官方文档来验证在实验中看到的行为。

sql-server

fragmentation

index

page-splits

回答 1

Database Administration用户

发布于 2011-04-29 13:00:02

如果在索引末尾添加一行，则只为该行分配一个新页，而不是拆分当前的结束页。这方面的实验证据如下(使用需要Server 2008的%%physloc%%函数)。也见这里的讨论。。

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

返回(您的结果将有所不同)

(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*/

不过，这似乎只适用于叶节点。通过运行下面的代码并调整TOP值就可以看出这一点。对我来说，622/623是需要一个和两个第一级页面之间的断点(如果启用了快照隔离，那么可能会有所不同)。它以平衡的方式分割页面，导致在这个级别上浪费空间。

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