[SQL SERVER]Bw(Buzz Word)- Tree 筆記

2014-12-06

1831
0
SQL_SERVER
2014-12-06

這篇我筆記 Bw-Tree 如何為in-memory帶來重大改善。

Bw-Tree 優點

1.針對範圍(range)和指標(point)搜尋有很高效率

2.自我平衡

3.每張 page 透過邏輯指標互相串起來

4.依照Key有順序存取

5.更有效率使用多CPU

這篇我會圍繞在Bw-tree Layer和Cache Layer。

Bw-Tree結構和b-tree結構類似，所有的leaf node依然還是資料頁(data page)，

不同的是所有leaf level都有一個指標(類似hash index 的bucket_count)，

其他index node只存放key(有順序)和下一頁指標

如此反覆處理直到在leaf node找到資料為止。

當要新增一筆資料(c1)到in-memory table時(假設該資料表有一hash index(c1))，

這時會擷取c1 value 並執行hash function，運算後會返回一個範圍值(依照該資料表上 bucket_count 定義)，

而該值(記憶體指標)將會被存放在一個對應表(Mapping Table)中，

由於每張 page都是使用邏輯指標(page identifiers or PID)串再一起，

最後透過該指標轉換指向資料所存放的物理位置，整個過程大概如下

Bw-tree ==> Mapping Table ==> Physical Page

由於每一次新增相同值，且經過hash function運算後都會得到相同結果，

所以相同結果都會被群組再一起(這可說大大節省了記憶體開銷)

透過這樣的儲存機制，當要改變一個page物理位置時，

只需改變所對應的Mapping Table，所以整個Bw-tree存取路徑並不會改變，

下面我簡單驗證一下Bw-tree 架構如何大大節省記憶體開銷。

--一般資料表

drop table disktbl
create table disktbl
(
 id int NOT NULL, 
 col1 varchar(100) COLLATE French_BIN2  NOT NULL  INDEX idx1 NONCLUSTERED,
   CONSTRAINT PK_disktbl PRIMARY KEY NONCLUSTERED (id) 
)

DECLARE @step INT 
SET @step = 1

WHILE @step <= 100000 
  BEGIN    

                   INSERT INTO dbo.disktbl 
      VALUES      (@step, 'rico1'),
                  (@step+1, 'rico2'),
                  (@step+2, 'rico3'),
                  (@step+3, 'rico4'),
                  (@step+4, 'rico5')

      SET @step = @step + 5
  END

--查看索引所使用大小

SELECT 
o.name as table_name,
i.[name] AS IndexName,
i.type_desc,
s.used_page_count
,SUM(s.[used_page_count]) * 8 AS IndexSizeKB
FROM sys.dm_db_partition_stats AS s
INNER JOIN sys.indexes AS i ON s.[object_id] = i.[object_id]
    AND s.[index_id] = i.[index_id]
INNER join sys.objects as o on o.object_id = i.object_id
where o.name='disktbl' and i.name='idx1'
GROUP BY o.name,i.[name],i.type_desc,s.used_page_count

idx1約使用4720 KB，pages:590

--in-memory 資料表

drop table memorytbl
CREATE TABLE memorytbl
(
       id int NOT NULL, 
       col1 varchar(100) COLLATE French_BIN2  NOT NULL  INDEX idx1 NONCLUSTERED,
       CONSTRAINT PK_mytest PRIMARY KEY NONCLUSTERED HASH (id) WITH (BUCKET_COUNT = 150000) 
) WITH (MEMORY_OPTIMIZED = ON, DURABILITY = SCHEMA_AND_DATA)

--新增10萬筆資料

DECLARE @step INT 
SET @step = 1

WHILE @step <= 100000 
  BEGIN    

                   INSERT INTO dbo.memorytbl 
      VALUES      (@step, 'rico1'),
                  (@step+1, 'rico2'),
                  (@step+2, 'rico3'),
                  (@step+3, 'rico4'),
                  (@step+4, 'rico5')

      SET @step = @step + 5
  END

--查看索引所使用大小

select
       o.name as table_name,
       i.name as index_name,              
       xmc.memory_consumer_desc,
       xmc.allocated_bytes / 1024 as allocated_kb,
       xmc.used_bytes
from sys.dm_db_xtp_memory_consumers as xmc
       join sys.indexes as i
             on xmc.object_id = i.object_id
                    and xmc.index_id = i.index_id
        join sys.objects as o
             on o.object_id = i.object_id
where i.name = 'idx1';

只使用952 bytes

--查看索引所使用page

in-memory 資料表

select
       o.name as table_name,
       i.name as index_name,
       nis.internal_pages,
       nis.delta_pages,
       nis.leaf_pages
from sys.dm_db_xtp_nonclustered_index_stats as nis
       join sys.objects as o
             on o.object_id = nis.object_id
       join sys.indexes as i
             on i.object_id = nis.object_id
                    and i.index_id = nis.index_id
where i.name = 'idx1';