Hai, nama saya Anton dan saya seorang pengembang. Anak saya melahirkan, rumah yang
Apa itu kumpulan bersarang
Semua orang tahu bagaimana pohon tumbuh di taman, dan dalam kasus kumpulan bersarang, pohon tumbuh seperti ini: untuk setiap node, dua bidang Kiri dan Kanan disimpan, mereka adalah bilangan bulat. Logikanya di sini adalah bahwa Kiri kurang dari Kanan, dan jika sebuah simpul memiliki anak, maka semua nilai Kiri dan Kanan dari simpul anak harus berada di antara nilai yang sesuai dari induknya.
Bagaimana mereka tumbuh bersama kita
Kami telah mendedikasikan layanan mikro terpisah untuk menyimpan hierarki. Fronted sering kali harus menggambar pohon lengkap serta subpohon elemen dalam tampilan detail, sementara elemen memasukkan dan memindahkan relatif jarang. Untuk kasus seperti itu, kumpulan bersarang sudah sempurna. Disimpan dalam tabel seperti ini:
Id adalah pengenal dari entitas yang sesuai, dengan menggunakannya Anda bisa mendapatkan informasi lengkap dari layanan mikro yang sesuai. TreeId adalah pengenal dari elemen root. Pohon-pohon di proyek ini kebanyakan kecil, tapi jumlahnya banyak. EntityFramework digunakan untuk membaca dari database, kelas terkait satu ke satu dengan struktur tabel.
Bagaimana cara membaca
Dengan metode penyimpanan ini, mendapatkan elemen subpohon itu sederhana - kami meminta semua node yang Kiri lebih besar dari Kiri induknya, dan Kanan, masing-masing lebih kecil. Kami juga memeriksa bahwa semua node dimiliki oleh pohon yang sama - menurut kolom TreeId. Ini adalah operasi yang paling sering dibutuhkan dan dilakukan dengan cepat. Misalnya seperti ini:
dataContext.Nodes.Where(_ =>
_.Left > node.Left &&
_.Right < node.Right &&
_.TreeId == node.TreeId);
Operasi lain yang sering dilakukan adalah menemukan semua node induk dari suatu objek. Di sini, juga, tidak sulit - kami meminta simpul pohon yang Kiri kurang dari Kiri elemen induk, dan Kanan lebih besar. Misalnya dengan cara ini:
dataContext.Nodes.Where(_ =>
_.Left < node.Left &&
_.Right > node.Right &&
_.TreeId == node.TreeId);
Cara menumbuhkan cabang baru
Mari beralih ke bagian yang sulit - transplantasi, mis. menambahkan node atau berpindah dari satu subpohon ke pohon lainnya. Mari kita cari tahu cara melakukan transfer, karena operasi ini pada dasarnya mencakup semua yang Anda butuhkan untuk menambahkan elemen anak.
Hal pertama yang harus dilakukan agar penyisipan berhasil adalah mengizinkan hanya satu operasi penyisipan atau pembaruan. Untuk melakukan ini, kami akan menggunakan pemblokiran. Tidak masuk akal untuk mengunci seluruh tabel, karena node hanya dapat menavigasi dalam satu pohon, jadi cukup mengunci hanya pohon ini. Untuk melakukan ini, jalankan kueri SQL berikut:
select * from "Nodes" where "TreeId" = <TreeId> for update; Ini akan memungkinkan kita untuk membaca elemen pohon dengan segera, tetapi jika kita perlu menambah atau mengubah simpul di pohon tempat operasi seperti itu telah dimulai, kita harus menunggu yang sebelumnya selesai.
Langkah selanjutnya adalah menyiapkan tempat untuk transplantasi - buat celah antara Kiri dan Kanan. Mari kita hitung berapa banyak ruang yang dibutuhkan - ini adalah perbedaan antara Kanan dan Kiri dari elemen akar pohon yang dipindahkan. Mari tambahkan perbedaan ini ke semua anak dari simpul yang akan menjadi induk baru. Kami dapat menangkap Exception di sini, dan inilah alasannya. Untuk mempercepat pencarian dan pembacaan dalam tabel, dua indeks B-Tree telah ditambahkan, pada field Kiri dan Kanan, dan jika Anda mengubah nilai dari field ini pada saat yang sama, EntityFramework mungkin memberikan kesalahan ketergantungan melingkar, karena dua indeks dapat dihitung ulang secara bersamaan dalam satu baris. Kesalahan akan menjadi jenis InvalidOperationException dengan pesan berikut:
Tidak dapat menyimpan perubahan karena ketergantungan melingkar terdeteksi pada data yang akan disimpan: 'Node [Modified] <- Index {' Right ',' TreeId '} Node [Modified] <- Index {' Left ',' TreeId '} Node [Dimodifikasi] '.
Untuk berkeliling, kita hanya akan membuat dua loop terpisah - di satu kita akan mengubah Kiri, di Kanan lainnya, dan, tentu saja, kita akan menyimpan perubahan setelah masing-masing.
var nodesToMove = await dataContext.Nodes
.Where(n =>
n.Right >= parentNodeRight &&
n.TreeId == parentNode.TreeId)
.OrderByDescending(n => n.Right)
.ToListAsync();
foreach (var n in nodesToMove)
{
n.Left += distance;
}
await dataContext.SaveChangesAsync();
foreach (var n in nodesToMove)
{
n.Right += distance;
}
await dataContext.SaveChangesAsync();
Selanjutnya, transplantasi itu sendiri - jarak transfer akan sama dengan perbedaan antara Kiri induk baru dan Kiri dari akar subtree. Tambahkan nilai ini ke Kiri dan Kanan dari semua simpul di pohon yang kita pindahkan.
var nodes = await dataContext.Nodes
.Where(n =>
n.Left >= node.Left &&
n.Right <= node.Right &&
n.TreeId == node.TreeId)
.ToListAsync();
foreach (var n in nodes)
{
n.Left += distance;
n.Right += distance;
Dan hal terakhir yang harus dilakukan adalah menutup celah tempat subpohon dipindahkan. Mari minta semua simpul di sebelah kanan pohon ini - ini akan menjadi elemen yang Haknya lebih besar dari atau sama dengan Kiri dari akar pohon, dan pindahkan ke ruang kosong. Untuk melakukan ini, kurangi dari Kiri dan Kanan semua node ini perbedaan antara Kanan dan Kiri dari root. Di sini, Anda juga harus melakukan dua putaran terpisah:
var nodesToMove = await dataContext.Nodes
.Where(n => n.Right >= gap.Left && n.TreeId == gap.TreeId)
.ToListAsync();
nodesToMove = nodesToMove
.Where(n => n.Right >= gap.Right)
.OrderBy(n => n.Right)
.ToList();
foreach (var n in nodesToMove)
{
if (n.Left >= gap.Right)
{
n.Left -= distance;
}
}
await dataContext.SaveChangesAsync();
foreach (var n in nodesToMove)
{
n.Right -= distance;
}
await dataContext.SaveChangesAsync();
Kesimpulan
Mari kita lihat apa yang telah berkembang. Kami mendapat pohon dengan kemampuan cepat membaca anak-anak dan orang tua. Jika proyek Anda perlu sering membaca data dan mengambil subpohon, kumpulan bersarang adalah pilihan yang bagus. Kita harus siap menghadapi kenyataan bahwa mungkin ada masalah dengan operasi penyisipan dan pembaruan, tetapi mereka cukup dapat dipecahkan. Jika Anda harus sering menambah dan mentransfer, lebih baik pikirkan tentang menggunakan beberapa algoritme lain, atau pertimbangkan beberapa opsi hibrid. Misalnya, silang kumpulan Bersarang dan Daftar Kedekatan. Untuk melakukan ini, di setiap node, selain Kiri dan Kanan, Anda perlu menambahkan tautan langsung ke pengenal elemen induk. Ini akan memungkinkan Anda untuk menavigasi hierarki dengan cepat dan menemukan node induk dan anak, dan, lebih dari itu, akan meningkatkan keandalan algoritme.