B-cây, cơ sở dữ liệu, tuần tự so với chèn ngẫu nhiên và tốc độ. Ngẫu nhiên đang thắng

Question

EDIT

@Remus đã sửa mẫu thử nghiệm của tôi. Bạn có thể xem phiên bản sửa chữa trên câu trả lời của mình bên dưới.

tôi đã đề nghị thay thế INT với DECIMAL (29,0) và kết quả là:

Decimal: 2133
GUID: 1836

chèn ngẫu nhiên vẫn đang chiến thắng, ngay cả với một hàng lớn hơn một phần.

Mặc dù các giải thích cho biết chèn ngẫu nhiên chậm hơn các chuỗi tuần tự, các điểm chuẩn này cho thấy chúng rõ ràng nhanh hơn. Những lời giải thích tôi nhận được không đồng ý với các tiêu chuẩn. Do đó, câu hỏi của tôi vẫn tập trung vào cây xanh, chèn liên tục và tốc độ.

...

tôi biết từ kinh nghiệm rằng b-cây có hiệu suất khủng khiếp khi dữ liệu được thêm vào chúng liên tục (không phân biệt hướng). Tuy nhiên, khi dữ liệu được thêm ngẫu nhiên, hiệu suất tốt nhất thu được.

Điều này rất dễ dàng để chứng minh với mức độ thích của RB-Tree. Việc ghi tuần tự gây ra số lượng cân bằng cây tối đa được thực hiện.

Tôi biết rất ít cơ sở dữ liệu sử dụng cây nhị phân, nhưng thay vì sử dụng các cây cân bằng n-trật tự. Tôi logic giả sử họ bị một số phận tương tự như cây nhị phân khi nói đến đầu vào tuần tự.

Điều này làm tôi tò mò.

Nếu điều này là như vậy, thì người ta có thể suy ra rằng việc viết các ID tuần tự (chẳng hạn như trong IDENTITY (1,1)) sẽ khiến nhiều số dư của cây xảy ra. Tôi đã thấy nhiều bài viết tranh luận chống lại GUID là "những điều này sẽ gây ra ghi ngẫu nhiên". Tôi không bao giờ sử dụng GUID, nhưng nó đánh tôi rằng điểm "xấu" này trên thực tế là một điểm tốt.

Vì vậy, tôi quyết định thử nghiệm nó. Đây là mã của tôi:

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 

Lưu ý rằng tôi không trừ bất cứ lúc nào cho việc tạo ra GUID cũng không cho kích thước thêm đáng kể của hàng. Các kết quả trên máy tính của tôi như sau:

Int: 17,340 ms GUID: 6746 ms

Điều này có nghĩa rằng trong thử nghiệm này, chèn ngẫu nhiên của 16 byte là gần 3 lần nhanh hơn hơn tuần tự chèn 4 byte.

Có ai muốn nhận xét về điều này không?

Ps. Tôi hiểu rằng đây không phải là một câu hỏi. Đó là lời mời thảo luận và điều đó có liên quan đến việc học lập trình tối ưu.

Answer 1

lật hoạt động và int nhanh hơn .. bạn đã đưa vào nhật ký tài khoản và tăng trưởng tệp dữ liệu chưa? Chạy riêng từng

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] 

vấn đề với UUIDs là khi phân nhóm vào chúng và không sử dụng NEWSEQUENTIALID() là họ gây ra ngắt trang và phân mảnh của bảng

bây giờ cố gắng như thế này và bạn sẽ thấy nó gần như là cùng

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()) 

Và ngược

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 2

tôi mong đợi trong việc tái cân bằng cơ sở dữ liệu thực sự của một chỉ mục là một vấn đề nhỏ, bởi vì rất nhiều mục chỉ mục sẽ phù hợp trong một khối duy nhất và lâu dài.

Điều gì có thể trở thành vấn đề hơn có thể gây tranh cãi cho khối duy nhất đó chứa tất cả các mục nhập mới. Oracle có một tính năng để lưu trữ các byte của khóa theo thứ tự ngược lại để truyền các mục mới ra trên tất cả các khối: http://oracletoday.blogspot.com/2006/09/there-is-option-to-create-index.html Không biết về các cơ sở dữ liệu khác.

Answer 3

Bạn không đo tốc độ INSERT. Bạn đang đo hiệu suất xả log của bạn. Vì bạn cam kết sau mỗi lần INSERT, tất cả những thử nghiệm đang làm đang ngồi xung quanh chờ cam kết làm cứng nhật ký. Đó là hầu như không có liên quan cho hiệu suất INSERT. Và xin đừng gửi các phép đo hiệu suất 'khi SET NOCOUNT là OFF ...

Vì vậy, cho phép thử này mà không cần thiết nhí server-client, với một dữ liệu đúng kích thước, hàng loạt cam kết và tiền phát triển cơ sở dữ liệu:

: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: 18s
GUIDS: 23s

QED