B-Tree-Node-Split-Strategie in SQL Server zur monoton steigenden Wertsteigerung

8

Stellen Sie sich einen B-Tree-Index für einen Wert vor, der immer monoton ansteigt, z. B. eine Spalte vom Typ IDENTITY. Bei einer herkömmlichen B-Tree-Implementierung wird ein Knoten, wenn er voll ist, zu 50% / 50% aufgeteilt, und wir erhalten einen B-Tree, in dem (fast) alle Knoten nur zu 50% voll sind.

Ich weiß, dass Oracle erkennt, wenn ein Wert ständig steigt, und in diesen Fällen führt Oracle stattdessen eine Aufteilung von 90% / 10% durch. Auf diese Weise sind (fast) alle Knoten zu 90% voll, und für diese häufig vorkommenden Fälle wird eine weitaus bessere Seitennutzung erzielt.

Ich konnte keine Dokumentation für eine ähnliche Funktion in SQL Server finden. Ich habe jedoch zwei Experimente durchgeführt, bei denen ich N zufällige Ganzzahlen und N aufeinanderfolgende Ganzzahlen in einen Index eingefügt habe. Der erstere Fall verwendete weit mehr Seiten, der letztere.

Bietet SQL Server eine ähnliche Funktionalität? Wenn ja: Können Sie mich auf eine Dokumentation zu dieser Funktion verweisen?

UPDATE: Durch die unten angegebenen Experimente scheinen die Blattknoten nicht geteilt zu sein und die internen Knoten sind zu 50% / 50% geteilt. Das macht B-Bäume bei zunehmenden Schlüsseln kompakter als bei zufälligen Schlüsseln. Der 90% / 10% -Ansatz von Oracle ist jedoch noch besser, und ich suche immer noch nach einer offiziellen Dokumentation, die das in Experimenten beobachtete Verhalten überprüfen kann.

someName
quelle
Eine akzeptable Antwort auf diese Frage scheint wahrscheinlich eine Dokumentation zu sein, in der alle Arten von Seitensplits aufgeführt sind, die auftreten können und wann sie auftreten können. Ich bin derzeit nicht bekannt solch eine Ressource , aber vielleicht jemand hier ist ...
Martin Smith

Antworten:

4

Wenn am Ende des Index eine Zeile hinzugefügt wird, wird der Zeile nur eine neue Seite zugewiesen, anstatt die aktuelle Endseite zu teilen. Experimentelle Beweise dafür finden Sie unten (verwendet die %%physloc%%Funktion, die SQL Server 2008 erfordert). Siehe auch die Diskussion hier .

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

Rückgabe (Ihre Ergebnisse variieren)

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

Dies scheint jedoch nur für Blattknoten zu gelten. Dies können Sie sehen, indem Sie die folgenden Schritte ausführen und den TOPWert anpassen . Für mich 622/623war der Grenzwert zwischen der Anforderung von einer und zwei Seiten der ersten Ebene (kann variieren, wenn Sie die Snapshot-Isolation aktiviert haben?). Die Seite wird ausgewogen aufgeteilt, was zu einer Verschwendung von Speicherplatz auf dieser Ebene führt.

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
Martin Smith
quelle
Vielen Dank. Beachten Sie jedoch, dass ich nach dem Verhalten der B-Tree-Indexknoten frage - nicht nach den Tabellenseiten. Interessante Lektüre. :-)
someName
1
@someName - Die Tabellenseiten sind die Blattknoten des Clusterindex, der implizit von der erstellt wurde PRIMARY KEY.
Martin Smith
Ah ich sehe. Diese Einfügestrategie ist sicherlich platzsparend. Aber ich sehe nicht, wie dies in die B-Baum-Struktur passt: Mit der Strategie "Zu einer neuen Seite hinzufügen statt zu teilen" erhalten wir eine lange verknüpfte Liste und keinen B-Baum. Wie werden bestimmte Werte nur mit einer logarithmischen Anzahl von Suchvorgängen (E / A) in dieser verknüpften Liste abgerufen?
someName
Dies ist nur die Blattknotenebene. Sobald die Blattknotenebene mehr als eine Seite hat, befindet sich eine weitere Ebene darüber. Sie können diese verwenden DBCC INDund sys.dm_db_index_physical_statsInformationen anzeigen.
Martin Smith
Aber wenn einer der Nicht-Blatt-Knoten voll ist, werde ich geteilt. Und diese Aufteilung, denke ich, beträgt 50% / 50%? Oder 90% / 10% wie Oracle?
someName