Data hierarkis (SQL Server)
Berlaku untuk: SQL ServerAzure SQL Database Azure SQL Managed Instance
Tipe data hierarkiid bawaan memudahkan penyimpanan dan kueri data hierarkis. hierarki dioptimalkan untuk mewakili pohon, yang merupakan jenis data hierarkis yang paling umum.
Data hierarkis didefinisikan sebagai sekumpulan item data yang terkait satu sama lain dengan hubungan hierarkis. Hubungan hierarkis ada di mana satu item data adalah induk dari item lain. Contoh data hierarkis yang umumnya disimpan dalam database mencakup item berikut:
- Struktur organisasi
- Sistem file
- Sekumpulan tugas dalam proyek
- Taksonomi istilah bahasa
- Grafik tautan antar halaman Web
Gunakan hierarkiid sebagai tipe data untuk membuat tabel dengan struktur hierarkis, atau untuk menjelaskan struktur hierarkis data yang disimpan di lokasi lain. Gunakan fungsi hierarkiid di Transact-SQL untuk mengkueri dan mengelola data hierarkis.
Properti utama
Nilai jenis data hierarkis mewakili posisi dalam hierarki pohon. Nilai untuk hierarkiid memiliki properti berikut:
Sangat ringkas
Jumlah rata-rata bit yang diperlukan untuk mewakili simpul di pohon dengan n simpul tergantung pada rata-rata fanout (jumlah rata-rata anak dari sebuah simpul). Untuk fanout kecil (0-7), ukurannya sekitar $6log{A}{n}$ bit, di mana A adalah fanout rata-rata. Simpul dalam hierarki organisasi 100.000 orang dengan kipas rata-rata enam tingkat membutuhkan sekitar 38 bit. Ini dibulatkan hingga 40 bit, atau 5 byte, untuk penyimpanan.
Perbandingan dalam urutan kedalaman pertama
Mengingat dua nilai
a
hierarkid danb
,a < b
berartia
datang sebelumb
di traversal kedalaman-pertama pohon. Indeks pada jenis data hierarkis berada dalam urutan yang mengutamakan kedalaman, dan simpul yang saling berdekatan dalam traversal yang mengutamakan kedalaman disimpan di dekat satu sama lain. Misalnya, anak-anak rekaman disimpan di samping rekaman tersebut.Dukungan untuk penyisipan dan penghapusan arbitrer
Dengan menggunakan metode GetDescendant (Mesin Database), selalu dimungkinkan untuk menghasilkan saudara kandung di sebelah kanan simpul tertentu, di sebelah kiri simpul tertentu, atau di antara dua saudara. Properti perbandingan dipertahankan ketika jumlah simpul arbitrer dimasukkan atau dihapus dari hierarki. Sebagian besar penyisipan dan penghapusan mempertahankan properti kekompakan. Namun, penyisipan antara dua simpul menghasilkan nilai hierarkiid dengan representasi yang sedikit kurang ringkas.
Batasan
Jenis data hierarki memiliki batasan berikut:
Kolom jenis hierarkiid tidak secara otomatis mewakili pohon. Terserah aplikasi untuk menghasilkan dan menetapkan nilai hierarkiid sedid sehingga hubungan yang diinginkan antar baris tercermin dalam nilai. Beberapa aplikasi mungkin memiliki kolom jenis hierarkiid yang menunjukkan lokasi dalam hierarki yang ditentukan dalam tabel lain.
Terserah aplikasi untuk mengelola konkurensi dalam menghasilkan dan menetapkan nilai hierarkiid . Tidak ada jaminan bahwa nilai hierarkiid dalam kolom unik kecuali aplikasi menggunakan batasan kunci unik atau memberlakukan keunikan itu sendiri melalui logikanya sendiri.
Hubungan hierarkis yang diwakili oleh nilai hierarkiid tidak diberlakukan seperti hubungan kunci asing. Dimungkinkan, dan kadang-kadang tepat, untuk memiliki hubungan hierarkis di mana
A
memiliki anakB
, dan kemudianA
dihapus meninggalkanB
dengan hubungan ke rekaman yang tidak ada. Jika perilaku ini tidak dapat diterima, aplikasi harus meminta turunan sebelum menghapus orang tua.
Kapan menggunakan alternatif untuk hierarkiid
Dua alternatif untuk hierarkiid untuk mewakili data hierarkis adalah:
- Induk/anak
- XML
hierarki umumnya lebih unggul daripada alternatif ini. Namun, ada situasi khusus, yang dirinci dalam artikel ini, di mana alternatifnya kemungkinan lebih unggul.
Induk/anak
Saat Anda menggunakan pendekatan induk/anak, setiap baris berisi referensi ke induk. Tabel berikut mendefinisikan tabel umum yang digunakan untuk berisi baris induk dan anak dalam hubungan induk/anak:
USE AdventureWorks2022;
GO
CREATE TABLE ParentChildOrg (
BusinessEntityID INT PRIMARY KEY,
ManagerId INT REFERENCES ParentChildOrg(BusinessEntityID),
EmployeeName NVARCHAR(50)
);
GO
Membandingkan induk/anak dan hierarkiid untuk operasi umum:
- Kueri subtree secara signifikan lebih cepat dengan hierarkiid.
- Kueri turunan langsung sedikit lebih lambat dengan hierarkis.
- Memindahkan simpul nonleaf lebih lambat dengan hierarkiid.
- Menyisipkan simpul nonleaf dan menyisipkan atau memindahkan simpul daun memiliki kompleksitas yang sama dengan hierarkiid.
Induk/anak mungkin lebih unggul ketika kondisi berikut ada:
Ukuran kunci sangat penting. Untuk jumlah node yang sama, nilai hierarkis sama dengan atau lebih besar dari nilai integer-family (smallint, int, bigint). Ini hanya alasan untuk menggunakan induk/anak dalam kasus yang jarang terjadi, karena hierarkiid memiliki lokalitas I/O dan kompleksitas CPU yang jauh lebih baik daripada ekspresi tabel umum yang diperlukan saat Anda menggunakan struktur induk/anak.
Kueri jarang dikueri di seluruh bagian hierarki. Dengan kata lain, kueri biasanya hanya membahas satu titik dalam hierarki. Dalam kasus ini, kolokasi tidak penting. Misalnya, induk/anak lebih unggul ketika tabel organisasi hanya digunakan untuk memproses penggajian untuk karyawan individu.
Subtree nonleaf sering bergerak dan performa sangat penting. Dalam representasi induk/turunan, mengubah lokasi baris dalam hierarki memengaruhi satu baris. Mengubah lokasi baris dalam penggunaan hierarkis mempengaruhi n baris, di mana n adalah jumlah simpul dalam subtree yang dipindahkan.
Jika subtree nonleaf sering bergerak dan performa penting, tetapi sebagian besar gerakan berada pada tingkat hierarki yang terdefinisi dengan baik, pertimbangkan untuk membagi tingkat yang lebih tinggi dan lebih rendah menjadi dua hierarki. Ini membuat semua perpindahan ke tingkat daun dari hierarki yang lebih tinggi. Misalnya, pertimbangkan hierarki situs Web yang dihosting oleh layanan. Situs berisi banyak halaman yang disusun secara hierarkis. Situs yang dihosting mungkin dipindahkan ke lokasi lain dalam hierarki situs, tetapi halaman bawahan jarang diatur ulang. Ini dapat diwakili melalui:
CREATE TABLE HostedSites ( SiteId HIERARCHYID, PageId HIERARCHYID ); GO
XML
Dokumen XML adalah pohon, dan oleh karena itu satu instans jenis data XML dapat mewakili hierarki lengkap. Di SQL Server saat indeks XML dibuat, nilai hierarkis digunakan secara internal untuk mewakili posisi dalam hierarki.
Menggunakan tipe data XML bisa lebih unggul jika semua hal berikut ini benar:
- Hierarki lengkap selalu disimpan dan diambil.
- Data digunakan dalam format XML oleh aplikasi.
- Pencarian predikat sangat terbatas dan tidak kritis performa.
Misalnya, jika aplikasi melacak beberapa organisasi, selalu menyimpan dan mengambil hierarki organisasi lengkap, dan tidak mengkueri ke dalam satu organisasi, tabel formulir berikut mungkin masuk akal:
CREATE TABLE XMLOrg (
Orgid INT,
Orgdata XML
);
GO
Strategi indeks untuk data hierarkis
Ada dua strategi untuk mengindeks data hierarkis:
Kedalaman-pertama
Indeks yang mengutamakan kedalaman menyimpan baris dalam subtree berdekatan satu sama lain. Misalnya, semua karyawan yang melapor melalui manajer disimpan di dekat catatan manajer mereka.
Dalam indeks yang mengutamakan kedalaman, semua simpul dalam subtree node dikolokasi. Oleh karena itu, indeks yang mengutamakan kedalaman efisien untuk menjawab kueri tentang subtree, seperti: "Temukan semua file di folder ini dan subfoldernya"
Luas-pertama
Indeks yang mengutamakan luas menyimpan baris setiap tingkat hierarki bersama-sama. Misalnya, catatan karyawan yang langsung melapor ke manajer yang sama disimpan di dekat satu sama lain.
Dalam indeks yang mengutamakan luas, semua anak langsung dari simpul dikolokasi. Oleh karena itu, indeks yang mengutamakan luas efisien untuk menjawab kueri tentang anak-anak segera, seperti: "Temukan semua karyawan yang melapor langsung ke manajer ini"
Apakah memiliki kedalaman terlebih dahulu, mengutamakan luas, atau keduanya, dan mana yang akan membuat kunci pengklusteran (jika ada), tergantung pada kepentingan relatif dari jenis kueri di atas, dan kepentingan relatif dari SELECT
operasi vs. DML. Untuk contoh terperinci strategi pengindeksan, lihat Tutorial: Menggunakan Jenis Data hierarkis.
Membuat indeks
Metode GetLevel() dapat digunakan untuk membuat urutan pertama yang luas. Dalam contoh berikut, indeks yang mengutamakan luas dan mengutamakan kedalaman dibuat:
USE AdventureWorks2022;
GO
CREATE TABLE Organization (
BusinessEntityID HIERARCHYID,
OrgLevel AS BusinessEntityID.GetLevel(),
EmployeeName NVARCHAR(50) NOT NULL
);
GO
CREATE CLUSTERED INDEX Org_Breadth_First
ON Organization (OrgLevel, BusinessEntityID);
GO
CREATE UNIQUE INDEX Org_Depth_First
ON Organization (BusinessEntityID);
GO
Contoh
Sampel kode Transact-SQL dalam artikel ini menggunakan AdventureWorks2022
database sampel atau AdventureWorksDW2022
, yang dapat Anda unduh dari halaman beranda Sampel Microsoft SQL Server dan Proyek Komunitas.
Contoh dasar
Contoh berikut sengaja disederhanakan untuk membantu Anda memulai. Pertama-tama buat tabel untuk menyimpan beberapa data geografi.
CREATE TABLE BasicDemo (
[Level] HIERARCHYID NOT NULL,
Location NVARCHAR(30) NOT NULL,
LocationType NVARCHAR(9) NULL
);
Sekarang sisipkan data untuk beberapa benua, negara/wilayah, negara bagian, dan kota.
INSERT BasicDemo
VALUES ('/1/', 'Europe', 'Continent'),
('/2/', 'South America', 'Continent'),
('/1/1/', 'France', 'Country'),
('/1/1/1/', 'Paris', 'City'),
('/1/2/1/', 'Madrid', 'City'),
('/1/2/', 'Spain', 'Country'),
('/3/', 'Antarctica', 'Continent'),
('/2/1/', 'Brazil', 'Country'),
('/2/1/1/', 'Brasilia', 'City'),
('/2/1/2/', 'Bahia', 'State'),
('/2/1/2/1/', 'Salvador', 'City'),
('/3/1/', 'McMurdo Station', 'City');
Pilih data, menambahkan kolom yang mengonversi data Tingkat menjadi nilai teks yang mudah dipahami. Kueri ini juga mengurutkan hasil berdasarkan jenis data hierarkis .
SELECT CAST([Level] AS NVARCHAR(100)) AS [Converted Level],
*
FROM BasicDemo
ORDER BY [Level];
Berikut set hasilnya.
Converted Level Level Location LocationType
--------------- -------- --------------- ---------------
/1/ 0x58 Europe Continent
/1/1/ 0x5AC0 France Country
/1/1/1/ 0x5AD6 Paris City
/1/2/ 0x5B40 Spain Country
/1/2/1/ 0x5B56 Madrid City
/2/ 0x68 South America Continent
/2/1/ 0x6AC0 Brazil Country
/2/1/1/ 0x6AD6 Brasilia City
/2/1/2/ 0x6ADA Bahia State
/2/1/2/1/ 0x6ADAB0 Salvador City
/3/ 0x78 Antarctica Continent
/3/1/ 0x7AC0 McMurdo Station City
Hierarki memiliki struktur yang valid, meskipun tidak konsisten secara internal. Bahia adalah satu-satunya negara bagian. Itu muncul dalam hierarki sebagai serekan kota Brasilia. Demikian pula, Stasiun McMurdo tidak memiliki negara/wilayah induk. Pengguna harus memutuskan apakah jenis hierarki ini sesuai untuk penggunaannya.
Tambahkan baris lain dan pilih hasilnya.
INSERT BasicDemo
VALUES ('/1/3/1/', 'Kyoto', 'City'),
('/1/3/1/', 'London', 'City');
SELECT CAST([Level] AS NVARCHAR(100)) AS [Converted Level],
*
FROM BasicDemo
ORDER BY [Level];
Ini menunjukkan lebih banyak kemungkinan masalah. Kyoto dapat dimasukkan sebagai tingkat /1/3/1/
meskipun tidak ada tingkat /1/3/
induk. Dan London dan Kyoto memiliki nilai yang sama untuk hierarkis. Sekali lagi, pengguna harus memutuskan apakah jenis hierarki ini sesuai untuk penggunaannya, dan memblokir nilai yang tidak valid untuk penggunaannya.
Selain itu, tabel ini tidak menggunakan bagian atas hierarki '/'
. Itu dihilangkan karena tidak ada induk umum dari semua benua. Anda dapat menambahkan satu dengan menambahkan seluruh planet.
INSERT BasicDemo
VALUES ('/', 'Earth', 'Planet');
Tugas terkait
Migrasi dari induk/turunan ke hierarkis
Sebagian besar pohon diwakili menggunakan induk/anak. Cara term mudah untuk bermigrasi dari struktur induk/anak ke tabel menggunakan hierarki adalah dengan menggunakan kolom sementara atau tabel sementara untuk melacak jumlah simpul di setiap tingkat hierarki. Untuk contoh migrasi tabel induk/anak, lihat pelajaran 1 Tutorial: Menggunakan Tipe Data hierarkis.
Mengelola pohon menggunakan hierarkiid
Meskipun kolom hierarkiid tidak selalu mewakili pohon, aplikasi dapat dengan mudah memastikan bahwa kolom tersebut melakukannya.
Saat membuat nilai baru, lakukan salah satu langkah berikut:
- Lacak nomor turunan terakhir di baris induk.
- Komputasi anak terakhir. Melakukan ini secara efisien membutuhkan indeks yang mengutamakan luas.
Menerapkan keunikan dengan membuat indeks unik pada kolom, mungkin sebagai bagian dari kunci pengklusteran. Untuk memastikan bahwa nilai unik disisipkan, lakukan salah satu langkah berikut:
- Deteksi kegagalan pelanggaran kunci unik dan coba lagi.
- Tentukan keunikan setiap simpul anak baru, dan masukkan sebagai bagian dari transaksi yang dapat diserialisasikan.
Contoh menggunakan deteksi kesalahan
Dalam contoh berikut, kode sampel menghitung nilai anak EmployeeId
baru, lalu mendeteksi pelanggaran kunci apa pun dan kembali ke INS_EMP
penanda untuk mengolah EmployeeId
ulang nilai untuk baris baru:
USE AdventureWorks;
GO
CREATE TABLE Org_T1 (
EmployeeId HIERARCHYID PRIMARY KEY,
OrgLevel AS EmployeeId.GetLevel(),
EmployeeName NVARCHAR(50)
);
GO
CREATE INDEX Org_BreadthFirst ON Org_T1 (
OrgLevel,
EmployeeId
);
GO
CREATE PROCEDURE AddEmp (
@mgrid HIERARCHYID,
@EmpName NVARCHAR(50)
)
AS
BEGIN
DECLARE @last_child HIERARCHYID;
INS_EMP:
SELECT @last_child = MAX(EmployeeId)
FROM Org_T1
WHERE EmployeeId.GetAncestor(1) = @mgrid;
INSERT INTO Org_T1 (EmployeeId, EmployeeName)
SELECT @mgrid.GetDescendant(@last_child, NULL), @EmpName;
-- On error, return to INS_EMP to recompute @last_child
IF @@error <> 0
GOTO INS_EMP
END;
GO
Contoh menggunakan transaksi yang dapat diserialisasikan
Indeks Org_BreadthFirst
memastikan bahwa menentukan @last_child
menggunakan pencarian rentang. Selain kasus kesalahan lain yang mungkin ingin diperiksa aplikasi, pelanggaran kunci duplikat setelah penyisipan menunjukkan upaya untuk menambahkan beberapa karyawan dengan ID yang sama, dan oleh karena itu @last_child
harus dikomputasi ulang. Kode berikut menghitung nilai simpul baru dalam transaksi yang dapat diserialisasikan:
CREATE TABLE Org_T2 (
EmployeeId HIERARCHYID PRIMARY KEY,
LastChild HIERARCHYID,
EmployeeName NVARCHAR(50)
);
GO
CREATE PROCEDURE AddEmp (
@mgrid HIERARCHYID,
@EmpName NVARCHAR(50)
)
AS
BEGIN
DECLARE @last_child HIERARCHYID;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN TRANSACTION;
SELECT @last_child = EmployeeId.GetDescendant(LastChild, NULL)
FROM Org_T2
WHERE EmployeeId = @mgrid;
UPDATE Org_T2
SET LastChild = @last_child
WHERE EmployeeId = @mgrid;
INSERT Org_T2 (EmployeeId, EmployeeName)
VALUES (@last_child, @EmpName);
COMMIT;
END;
Kode berikut mengisi tabel dengan tiga baris dan mengembalikan hasilnya:
INSERT Org_T2 (EmployeeId, EmployeeName)
VALUES (HIERARCHYID::GetRoot(), 'David');
GO
AddEmp 0x, 'Sariya'
GO
AddEmp 0x58, 'Mary'
GO
SELECT * FROM Org_T2
Berikut set hasilnya.
EmployeeId LastChild EmployeeName
---------- --------- ------------
0x 0x58 David
0x58 0x5AC0 Sariya
0x5AC0 NULL Mary
Menerapkan pohon
Contoh sebelumnya menggambarkan bagaimana aplikasi dapat memastikan bahwa pohon dipertahankan. Untuk menerapkan pohon dengan menggunakan batasan, kolom komputasi yang menentukan induk setiap simpul dapat dibuat dengan batasan kunci asing kembali ke ID kunci utama.
CREATE TABLE Org_T3 (
EmployeeId HIERARCHYID PRIMARY KEY,
ParentId AS EmployeeId.GetAncestor(1) PERSISTED REFERENCES Org_T3(EmployeeId),
LastChild HIERARCHYID,
EmployeeName NVARCHAR(50)
);
GO
Metode memberlakukan hubungan ini lebih disukai ketika kode yang tidak dipercaya untuk mempertahankan pohon hierarkis memiliki akses DML langsung ke tabel. Namun metode ini dapat mengurangi performa karena batasan harus diperiksa pada setiap operasi DML.
Temukan leluhur dengan menggunakan CLR
Operasi umum yang melibatkan dua simpul dalam hierarki adalah menemukan leluhur umum terendah. Tugas ini dapat ditulis dalam Transact-SQL atau CLR, karena jenis hierarkis tersedia di keduanya. CLR direkomendasikan karena performa lebih cepat.
Gunakan kode CLR berikut untuk mencantumkan leluhur dan untuk menemukan leluhur umum terendah:
using System;
using System.Collections;
using System.Text;
using Microsoft.SqlServer.Server; // SqlFunction Attribute
using Microsoft.SqlServer.Types; // SqlHierarchyId
public partial class HierarchyId_Operations
{
[SqlFunction(FillRowMethodName = "FillRow_ListAncestors")]
public static IEnumerable ListAncestors(SqlHierarchyId h)
{
while (!h.IsNull)
{
yield return (h);
h = h.GetAncestor(1);
}
}
public static void FillRow_ListAncestors(
Object obj,
out SqlHierarchyId ancestor
)
{
ancestor = (SqlHierarchyId)obj;
}
public static HierarchyId CommonAncestor(
SqlHierarchyId h1,
HierarchyId h2
)
{
while (!h1.IsDescendantOf(h2))
{
h1 = h1.GetAncestor(1);
}
return h1;
}
}
Untuk menggunakan ListAncestor
metode dan CommonAncestor
dalam contoh Transact-SQL berikut, buat DLL dan buat HierarchyId_Operations
rakitan di SQL Server dengan menjalankan kode yang mirip dengan contoh berikut:
CREATE ASSEMBLY HierarchyId_Operations
FROM '<path to DLL>\ListAncestors.dll';
GO
Mencantumkan leluhur
Membuat daftar leluhur simpul adalah operasi umum, misalnya untuk menunjukkan posisi dalam organisasi. Salah satu cara untuk melakukan ini adalah dengan menggunakan fungsi bernilai tabel menggunakan kelas yang HierarchyId_Operations
ditentukan sebelumnya:
Menggunakan Transact-SQL:
CREATE FUNCTION ListAncestors (@node HIERARCHYID)
RETURNS TABLE (node HIERARCHYID)
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.ListAncestors;
GO
Contoh penggunaan:
DECLARE @h HIERARCHYID
SELECT @h = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\janice0' -- /1/1/5/2/
SELECT LoginID,
OrgNode.ToString() AS LogicalNode
FROM HumanResources.EmployeeDemo AS ED
INNER JOIN ListAncestors(@h) AS A
ON ED.OrgNode = A.Node
GO
Temukan nenek moyang umum terendah
Dengan menggunakan kelas yang HierarchyId_Operations
ditentukan sebelumnya, buat fungsi Transact-SQL berikut untuk menemukan leluhur umum terendah yang melibatkan dua simpul dalam hierarki:
CREATE FUNCTION CommonAncestor (
@node1 HIERARCHYID,
@node2 HIERARCHYID
)
RETURNS HIERARCHYID
AS
EXTERNAL NAME HierarchyId_Operations.HierarchyId_Operations.CommonAncestor;
GO
Contoh penggunaan:
DECLARE @h1 HIERARCHYID, @h2 HIERARCHYID;
SELECT @h1 = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\jossef0';-- Node is /1/1/3/
SELECT @h2 = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = 'adventure-works\janice0';-- Node is /1/1/5/2/
SELECT OrgNode.ToString() AS LogicalNode, LoginID
FROM HumanResources.EmployeeDemo
WHERE OrgNode = dbo.CommonAncestor(@h1, @h2);
Node yang dihasilkan adalah /1/1/
Memindahkan subtrees
Operasi umum lainnya adalah memindahkan subtrees. Prosedur berikut mengambil subtree dan @oldMgr
menjadikannya (termasuk @oldMgr
) subtree dari @newMgr
.
CREATE PROCEDURE MoveOrg (
@oldMgr NVARCHAR(256),
@newMgr NVARCHAR(256)
)
AS
BEGIN
DECLARE @nold HIERARCHYID, @nnew HIERARCHYID;
SELECT @nold = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = @oldMgr;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
BEGIN TRANSACTION;
SELECT @nnew = OrgNode
FROM HumanResources.EmployeeDemo
WHERE LoginID = @newMgr;
SELECT @nnew = @nnew.GetDescendant(max(OrgNode), NULL)
FROM HumanResources.EmployeeDemo
WHERE OrgNode.GetAncestor(1) = @nnew;
UPDATE HumanResources.EmployeeDemo
SET OrgNode = OrgNode.GetReparentedValue(@nold, @nnew)
WHERE OrgNode.IsDescendantOf(@nold) = 1;
COMMIT TRANSACTION;
END;
GO