B-деревья, базы данных, последовательная и случайная вставка и скорость. Случайный выигрыш

EDIT

@Remus исправил мой тестовый шаблон. Вы можете увидеть исправленную версию в его ответе ниже. GUID: 1836

Случайные вставки по-прежнему выигрывают, даже с дробно большей строкой.

Несмотря на объяснения, указывающие на то, что случайные вставки медленнее, чем последовательные, эти тесты показывают, что они явно быстрее. Объяснения, которые я получаю, не согласуются с тестами. Поэтому мой вопрос по-прежнему сосредоточен на b-деревьях, последовательных вставках и скорости.

...

Я знаю по опыту, что b-деревья имеют ужасную производительность, когда данные добавляются к ним последовательно (независимо от направления) . Однако, когда данные добавляются случайным образом, достигается лучшая производительность.

Это легко продемонстрировать с подобными RB-Tree. Последовательная запись приводит к выполнению максимального числа балансировок деревьев.

Я знаю, что очень немногие базы данных используют двоичные деревья, а скорее используют сбалансированные деревья n-го порядка. Я логично предполагаю, что они постигают ту же участь, что и бинарные деревья, когда дело доходит до последовательных входов.

Это вызвало у меня любопытство.

Если это так, то можно сделать вывод, что запись последовательных идентификаторов (например, в IDENTITY (1, 1)) приведет к многократной перебалансировке дерева. Я видел , что во многих сообщениях высказывались возражения против GUID, поскольку «они вызывают случайную запись». Я никогда не использую GUID, но меня поразило, что эта «плохая» точка на самом деле была хорошей точкой.

Поэтому я решил ее протестировать. Вот мой код:

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[T1](
    [ID] [int] NOT NULL
 CONSTRAINT [T1_1] PRIMARY KEY CLUSTERED ([ID] ASC) 
)
GO

CREATE TABLE [dbo].[T2](
    [ID] [uniqueidentifier] NOT NULL
 CONSTRAINT [T2_1] PRIMARY KEY CLUSTERED ([ID] ASC)
)

GO

declare @i int, @t1 datetime, @t2 datetime, @t3 datetime, @c char(300)

set @t1 = GETDATE()
set @i = 1

while @i < 2000 begin
    insert into T2 values (NEWID(), @c)
    set @i = @i + 1
end

set @t2 = GETDATE()
WAITFOR delay '0:0:10'
set @t3 = GETDATE()
set @i = 1

while @i < 2000 begin
    insert into T1 values (@i, @c)
    set @i = @i + 1
end

select DATEDIFF(ms, @t1, @t2) AS [Int], DATEDIFF(ms, @t3, getdate()) AS [GUID]

drop table T1
drop table T2

Обратите внимание, что я не вычитаю время на создание GUID или из-за значительно большего размера строки. Результаты на моей машине были следующими:

Int: 17,340 мс.

Если это так, то можно сделать вывод, что запись последовательных идентификаторов (например, в IDENTITY (1,1)) вызовет множественные перебалансировки дерева. Я видел , что во многих сообщениях высказывались возражения против GUID, поскольку «это вызовет случайную запись». Я никогда не использую GUID, но меня поразило, что эта «плохая» точка на самом деле была хорошей точкой.

Поэтому я решил проверить ее. Вот мой код:

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[T1](
    [ID] [int] NOT NULL
 CONSTRAINT [T1_1] PRIMARY KEY CLUSTERED ([ID] ASC) 
)
GO

CREATE TABLE [dbo].[T2](
    [ID] [uniqueidentifier] NOT NULL
 CONSTRAINT [T2_1] PRIMARY KEY CLUSTERED ([ID] ASC)
)

GO

declare @i int, @t1 datetime, @t2 datetime, @t3 datetime, @c char(300)

set @t1 = GETDATE()
set @i = 1

while @i < 2000 begin
    insert into T2 values (NEWID(), @c)
    set @i = @i + 1
end

set @t2 = GETDATE()
WAITFOR delay '0:0:10'
set @t3 = GETDATE()
set @i = 1

while @i < 2000 begin
    insert into T1 values (@i, @c)
    set @i = @i + 1
end

select DATEDIFF(ms, @t1, @t2) AS [Int], DATEDIFF(ms, @t3, getdate()) AS [GUID]

drop table T1
drop table T2

Обратите внимание, что я не вычитаю время на создание GUID или из-за значительно большего размера строки. Результаты на моей машине были следующими:

Int: 17,340 мс.

Если это так, то можно сделать вывод, что запись последовательных идентификаторов (например, в IDENTITY (1,1)) вызовет множественные перебалансировки дерева. Я видел , что во многих сообщениях высказывались возражения против GUID, поскольку «это вызовет случайную запись». Я никогда не использую GUID, но меня поразило, что эта «плохая» точка на самом деле была хорошей точкой.

Поэтому я решил проверить ее. Вот мой код:

SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE TABLE [dbo].[T1](
    [ID] [int] NOT NULL
 CONSTRAINT [T1_1] PRIMARY KEY CLUSTERED ([ID] ASC) 
)
GO

CREATE TABLE [dbo].[T2](
    [ID] [uniqueidentifier] NOT NULL
 CONSTRAINT [T2_1] PRIMARY KEY CLUSTERED ([ID] ASC)
)

GO

declare @i int, @t1 datetime, @t2 datetime, @t3 datetime, @c char(300)

set @t1 = GETDATE()
set @i = 1

while @i < 2000 begin
    insert into T2 values (NEWID(), @c)
    set @i = @i + 1
end

set @t2 = GETDATE()
WAITFOR delay '0:0:10'
set @t3 = GETDATE()
set @i = 1

while @i < 2000 begin
    insert into T1 values (@i, @c)
    set @i = @i + 1
end

select DATEDIFF(ms, @t1, @t2) AS [Int], DATEDIFF(ms, @t3, getdate()) AS [GUID]

drop table T1
drop table T2

Обратите внимание, что я не вычитаю время на создание GUID или из-за значительного увеличения размера строки. Результаты на моей машине были следующими:

Int: 17,340 мс. GUID: 6 746 мс

Это означает, что в этом тесте случайные вставки 16 байтов были почти в 3 раза быстрее , чем последовательные вставки 4 байтов . 12123] Кто-нибудь хотел бы это прокомментировать?

Пс. Я понимаю, что это не вопрос. Это приглашение к дискуссии, и оно имеет отношение к изучению оптимального программирования.