Data Hierarkis (SQL Server)

Artikel
08/21/2023

Berlaku untuk:SQL Server Azure 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 meliputi yang berikut ini:

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 hierarkis

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 6*logAn bit, di mana A adalah fanout rata-rata. Simpul dalam hierarki organisasi 100.000 orang dengan kipas rata-rata 6 tingkat membutuhkan sekitar 38 bit. Ini dibulatkan hingga 40 bit, atau 5 byte, untuk penyimpanan.
Perbandingan dalam urutan kedalaman pertama

Mengingat dua nilai hierarkis a dan b, a<b berarti datang sebelum b dalam traversal pohon yang mengutamakan kedalaman. 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 berdekatan dengan rekaman tersebut.
Dukungan untuk penyisipan dan penghapusan arbitrer

Dengan menggunakan metode GetDescendant , selalu dimungkinkan untuk menghasilkan saudara kandung di sebelah kanan simpul tertentu, di sebelah kiri simpul tertentu, atau di antara dua saudara kandung. 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 akan menghasilkan nilai hierarkiid dengan representasi yang sedikit kurang ringkas.

Batasan hierarkis

Jenis data hierarki memiliki batasan berikut:

Kolom jenis hierarkiid tidak secara otomatis mewakili pohon. Terserah aplikasi untuk menghasilkan dan menetapkan nilai hierarkiid sedih 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 anak B, dan kemudian A dihapus meninggalkan B dengan hubungan ke catatan yang tidak ada. Jika perilaku ini tidak dapat diterima, aplikasi harus meminta turunan sebelum menghapus orang tua.

Kapan Menggunakan Alternatif untuk hierarkis

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 di bawah ini di mana alternatif kemungkinan lebih unggul.

Induk/Anak

Saat Anda menggunakan pendekatan Induk/Anak, setiap baris berisi referensi ke induk. Tabel berikut menentukan 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 non-daun lebih lambat dengan hierarkisid.
Menyisipkan node non-daun 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 lokasi bersama tidak penting. Misalnya, Induk/Anak lebih unggul ketika tabel organisasi hanya digunakan untuk memproses penggajian untuk karyawan individu.
Subtree non-daun sering bergerak dan performa sangat penting. Dalam representasi induk/turunan yang mengubah lokasi baris dalam hierarki memengaruhi satu baris. Mengubah lokasi baris dalam penggunaan hierarkis mempengaruhi n baris, di mana n adalah jumlah simpul di sub-pohon yang dipindahkan.

Jika subtrees non-daun 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 Pengindeksan 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 berada di lokasi yang sama. 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 berada bersama. 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 operasi SELECT 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;   -- wmimof
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

Contoh sederhana

Contoh berikut sengaja disederhanakan untuk membantu Anda memulai. Pertama-tama buat tabel untuk menyimpan beberapa data geografi.

CREATE TABLE SimpleDemo  
(
    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 SimpleDemo  
    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 SimpleDemo ORDER BY Level;

Berikut adalah hasil yang ditetapkan.

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

Perhatikan bahwa 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 atau wilayah induk. Pengguna harus memutuskan apakah jenis hierarki ini sesuai untuk penggunaannya.

Tambahkan baris lain dan pilih hasilnya.

INSERT SimpleDemo  
    VALUES ('/1/3/1/', 'Kyoto', 'City'), ('/1/3/1/', 'London', 'City');  
SELECT CAST(Level AS nvarchar(100)) AS [Converted Level], * FROM SimpleDemo 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 SimpleDemo  
    VALUES ('/', 'Earth', 'Planet');

Tugas Terkait

Migrasi dari Induk/Anak 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 hal berikut ini:
- 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 hal berikut ini:
- 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 EmployeeId anak baru, lalu mendeteksi pelanggaran kunci dan kembali ke penanda INS_EMP untuk mengkomputasi ulang nilai EmployeeId 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 adalah hasil yang ditetapkan.

EmployeeId LastChild EmployeeName  
---------- --------- ------------  
0x        0x58       David  
0x58      0x5AC0     Sariya  
0x5AC0    NULL       Mary

Memberlakukan pohon

Contoh di atas 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.

Menemukan Leluhur dengan Menggunakan CLR

Operasi umum yang melibatkan dua simpul dalam hierarki adalah menemukan leluhur umum terendah. Ini dapat ditulis dalam Transact-SQL atau CLR, karena jenis hierarkis tersedia di keduanya. CLR direkomendasikan karena performa akan 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 metode ListAncestor dan CommonAncestor dalam contoh Transact-SQL berikut, buat DLL dan buat rakitan HierarchyId_Operations di SQL Server dengan menjalankan kode yang mirip dengan yang berikut ini:

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 HierarchyId_Operations yang ditentukan di atas:

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  
JOIN ListAncestors(@h) AS A   
   ON ED.OrgNode = A.Node  
GO

Menemukan Leluhur Umum Terendah

Dengan menggunakan kelas HierarchyId_Operations yang ditentukan di atas, 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