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

Question

РЕДАКТИРОВАТЬ

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

Я принял предложение заменить INT на DECIMAL (29,0), и результаты были такими:

Десятичное число: 2133
GUID: 1836

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

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

...

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

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

Я знаю, что очень немногие базы данных используют двоичные деревья, но используют сбалансированные деревья 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 мс GUID: 6,746 мс

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

Кто-нибудь хотел бы прокомментировать это?

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

Answer 1

Вы не измеряете скорость ВСТАВКИ.Вы измеряете производительность вашего журнала.Поскольку вы выполняете коммит после каждой INSERT, все эти тесты сидят без дела, ожидая коммита, чтобы укрепить журнал.Это вряд ли относится к производительности INSERT.И, пожалуйста, не публикуйте измерения «производительности», когда SET NOCOUNT равен OFF ...

Так что давайте попробуем это без лишних разговоров сервер-клиент, с данными надлежащего размера, пакетными коммитами и предварительно выращенными базами данных.:

:setvar dbname testdb
:setvar testsize 1000000
:setvar batchsize 1000

use master;
go

if db_id('$(dbname)') is not null
begin
    drop database [$(dbname)];
end
go

create database [$(dbname)] 
    on (name='test_data', filename='c:\temp\test_data.mdf', size=10gb)
    log on (name='test_log', filename='c:\temp\test_log.ldf', size=100mb);
go

use [$(dbname)];
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

set nocount on;
go

declare @i int, @t1 datetime, @t2 datetime

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

begin transaction;
while @i < $(testsize) begin
    insert into T1 values (@i)
    set @i = @i + 1
    if @i % $(batchsize) = 0
    begin
        commit;
        begin transaction;
    end
end
commit

set @t2 = GETDATE()
set @i = 1
begin transaction
while @i < $(testsize) begin
    insert into T2 values (NEWID())
    set @i = @i + 1
    if @i % $(batchsize) = 0
    begin
        commit;
        begin transaction;
    end
end
commit

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

drop table T1
drop table T2

INTS: 18 с
НАПРАВЛЯЮЩИЕ: 23 с

КЭД

Answer 2

переверните операцию, и int быстрее .. Вы учли рост журнала и файла данных?Запускайте каждый из них отдельно

declare @i int, @t1 datetime, @t2 datetime

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

while @i < 10000 begin
    insert into T2 values (NEWID())
    set @i = @i + 1
END


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

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



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

. Проблема с UUID заключается в том, что при кластеризации по ним и при отсутствии NEWSEQUENTIALID () они вызывают разрывы страниц и фрагментацию таблицы

.вижу, это почти то же самое

declare @i int, @t1 datetime, @t2 datetime

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

while @i < 10000 begin
    insert into T2 values (NEWID())
    set @i = @i + 1
END
select DATEDIFF(ms, @t1, getdate()) 

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

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



select DATEDIFF(ms, @t1, getdate())

и наоборот

declare @i int, @t1 datetime, @t2 datetime



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

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

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

while @i < 10000 begin
    insert into T2 values (NEWID())
    set @i = @i + 1
END
select DATEDIFF(ms, @t1, getdate())

Answer 3

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

То, что может стать более серьезной проблемой, может привести к конфликту с этим единственным блоком, содержащим все новые записи. В Oracle есть функция хранения байтов ключа в обратном порядке для распределения новых записей по всем блокам: http://oracletoday.blogspot.com/2006/09/there-is-option-to-create-index.html Не знаю о других базах данных.