Thật dễ dàng để giải thích bằng các ví dụ hơn là một vài từ. Hãy xem xét cây mẫu, lưu trữ tên:
William
Jones
Blake
Adams
Tyler
Joseph
Miller
Flint
Đường dẫn vật chất có nghĩa là mỗi nút lưu trữ toàn bộ đường dẫn được mã hóa. Ví dụ, bạn có thể lưu trữ chỉ số của nó bằng một dấu chấm như một delimiter
Name Path
William 1
Jones 1.1
Blake 1.2
Adams 1.2.1
Tyler 1.3
Joseph 2
Miller 2.1
Flint 2.2
Vì vậy, Adams biết tên đầy đủ của nó là William Blake Adams, bởi vì nó có con đường 1.2.1, trỏ đến các 1 nút ở cấp đầu tiên - William - tới nút 1.2 ở cấp 2 - Blake - và 1.2.1 nút ở cấp 3 - Adams.
Danh sách adjacency có nghĩa là cây được lưu trữ bằng cách giữ liên kết đến một số nút lân cận. Ví dụ, bạn có thể lưu trữ ai là cha mẹ và ai là anh chị em tiếp theo.
Name Parent Next
William null Joseph
Jones William Blake
Blake William Tyler
Adams Blake null
Tyler William null
Joseph null null
Miller Joseph Flint
Flint Joseph null
Lưu ý rằng nó có thể đơn giản như chỉ lưu trữ phụ huynh, nếu chúng ta không cần giữ con của nút được sắp xếp. Bây giờ Adams có thể nhận được tất cả các tổ tiên của mình đệ quy cho đến khi null để tìm tên đầy đủ của mình.
Bộ lồng nhau có nghĩa là bạn lưu trữ mỗi nút với một số chỉ mục, thường là giá trị trái và phải, được gán cho mỗi nút khi bạn duyệt cây theo thứ tự DFS, vì vậy bạn biết con cháu của nó nằm trong các giá trị đó. Đây là cách các con số sẽ được gán cho cây dụ:
1 William 10
2 Jones 3
4 Blake 7
5 Adams 6
8 Tyler 9
11 Joseph 16
12 Miller 13
14 Flint 15
Và nó sẽ được lưu trữ như:
Name left right
William 1 10
Jones 2 3
Blake 4 7
Adams 5 6
Tyler 8 9
Joseph 11 16
Miller 12 13
Flint 14 15
Vì vậy, bây giờ Adams có thể tìm thấy tổ tiên của mình bằng cách truy vấn những người có một trái thấp hơn và giá trị bên phải cao hơn và sắp xếp chúng theo giá trị bên trái.
Mỗi mô hình đều có điểm mạnh và điểm yếu. Chọn cái nào để sử dụng thực sự phụ thuộc vào ứng dụng của bạn, cơ sở dữ liệu bạn đang sử dụng và loại hoạt động nào bạn sẽ làm thường xuyên nhất. Bạn có thể tìm thấy một so sánh tốt here.
So sánh đề cập đến mô hình thứ tư không phổ biến (tôi không biết về bất kỳ triển khai nào khác nhưng của riêng tôi) và rất phức tạp để giải thích bằng một vài từ: Khoảng thời gian lồng nhau thông qua Mã hóa ma trận.
Khi bạn chèn một nút mới trong tập hợp lồng nhau, bạn phải liệt kê lại tất cả những người đứng trước nó trong quá trình truyền tải. Ý tưởng đằng sau khoảng thời gian lồng nhau là có vô số các số hữu tỷ giữa hai số nguyên, vì vậy bạn có thể lưu trữ nút mới dưới dạng một phần nhỏ của các nút trước đó và tiếp theo của nó.Việc lưu trữ và truy vấn các phân số có thể rắc rối, và điều này dẫn đến kỹ thuật mã hóa ma trận, biến đổi các phân số đó thành ma trận 2x2 và hầu hết các phép toán có thể được thực hiện bởi một số đại số ma trận không rõ ràng ngay từ lần đầu tiên nhưng có thể rất hiệu quả.
Treebeard có triển khai rất đơn giản của từng đường dẫn vật hoá, tập hợp lồng nhau và danh sách adjacency, không có dự phòng. django-mptt thực sự sử dụng một tập hợp các Nested Sets và Adjacency Lists, vì nó cũng giữ một liên kết đến parent và có thể sử dụng nó cho cả hai query child một cách hiệu quả hơn, và xây dựng lại cây trong trường hợp nó bị sai lầm bởi ai đó.