Cách cấu trúc cơ sở dữ liệu để truy cập nút nhanh

Question

Tôi đang tìm cách cấu trúc cơ sở dữ liệu với cơ sở dữ liệu VirtualTreeView và SQLite để truy xuất nhanh dữ liệu. Với VirtualTreeView có một sự kiện OnNodeInit bu nó không phải là luôn luôn thực tế cho mục đích này.

Dữ liệu được tìm nạp từ các nhóm tin Usenet và cần được tạo luồng. Dữ liệu hữu ích cho luồng là bài id (int64, cũng chính khóa), tài liệu tham khảo (chuỗi tham chiếu đến các bài viết trước trong chủ đề).

Chương trình tìm kiếm các chuỗi trong tham chiếu và xác định trong đó postid cần đi. Vì vậy, ví dụ bài id = 1234, sau đó bài tiếp theo có thể là 1235, và sau đó năm 1236 có thể trả lời cho 1234.

Đây là một cơ sở dữ liệu có thể ví dụ:

post id references parent id 
    1234  .... ....  0 
    1235  .... ....  0 
    1236  .... ....  1234 

Vì vậy, bây giờ điều này là làm thế nào nó có vẻ đúng hiện nay.

Bây giờ, sự cố là cách cấu trúc dữ liệu này để truy xuất nhanh hơn. Nếu chỉ có một nút gốc, tôi có thể gán RootNodeCount dựa trên các mục cơ sở dữ liệu và sau đó trong OnNodeInit hãy đọc từng cái một theo yêu cầu. Khi có các nút con thì tôi cần phải sắp xếp lại cơ sở dữ liệu bằng cách nào đó để nó biết làm thế nào để có được các nút con nhanh hơn tùy thuộc vào nút nào được mở.

Tôi đã suy nghĩ gán trường bổ sung "has_subnodes" với ID của nút con sau. Khi một nút được nhấp, nút đó sẽ đọc nút đó và mọi nút được liên kết.

Bạn sẽ tổ chức cơ sở dữ liệu này như thế nào để có thể đọc độc đáo trong OnNodeInit hoặc bạn có sử dụng sự kiện đó không? Các nút cũng có thể được khởi tạo bằng phương thức AddChildNoInit(). Bất kỳ ý tưởng hoặc con trỏ sẽ được chào đón.

CẬP NHẬT (AND cách tôi giải quyết CNTT)

Có một số thông tin không virtualtreeview liên quan có sẵn ở đây: Implementing a hierarchical data structure in a database

Những gì tôi đã kết thúc làm là sử dụng Modified Preorder Tree Traversal để lưu trữ thông tin trong cơ sở dữ liệu về các nút và mỗi lần một nút nhất định được yêu cầu đầu tiên:

a) nó được tra cứu trong bộ nhớ cache nội bộ về cơ bản giữ cấu trúc giống hệt với cấu trúc VirtualTreeView.

b) nếu tìm thấy trong bộ nhớ cache, cache entry này được lấy ra (nó không bao giờ nắm giữ hơn 100 bài)

c) nếu không tìm thấy, thêm 100 mặt hàng được thêm vào trong bộ nhớ cache (50 lên từ nút yêu cầu, và 50 xuống). Số lượng khóa học này có thể được sửa đổi thành 500 hoặc 1000 mục nếu cần. Có một số kiểm tra bổ sung để xem có bao nhiêu lên/xuống nó cần phải đọc để tránh đọc quá nhiều mục trùng lặp.

d) nếu tôi cần tốc độ cao hơn, tôi có thể áp dụng các nút tải kỹ thuật bổ sung từ cơ sở dữ liệu dựa trên số lượng người dùng cuộn virtualtreeview - tương tự như cách std :: vector cấp phát bộ nhớ - trước tiên tôi chỉ tải 100 nút, sau đó người dùng cuộn rất nhiều, tôi tải 200, sau đó 400 vv ... người dùng càng cuộn nhanh hơn nó tải toàn bộ cây nhưng vẫn không tải nó nếu anh/cô ấy không bao giờ cuộn.

Bằng cách này, các nút không bao giờ được nhìn thấy sẽ không bao giờ được tải từ cơ sở dữ liệu. Nó hoạt động tốt khi cuộn bằng bánh xe chuột (thỉnh thoảng có độ trễ ngắn khi nó vượt qua điểm mà bộ nhớ cache trống và cần thêm dữ liệu từ đĩa) và để cuộn bằng các nút/phím mũi tên.Đó là một chút chậm hơn khi bạn kéo thanh cuộn đến vị trí nhất định (nói từ dưới lên giữa) nhưng điều đó được mong đợi vì dữ liệu không thể được lấy từ đĩa ngay lập tức. Nó là tốt nhất nếu tôi xác định trước bao nhiêu bộ nhớ tôi muốn sử dụng cho bộ nhớ cache/mục trước khi tải chúng, càng có nhiều cuộn nhanh hơn nhưng tất nhiên sau đó nó sử dụng nhiều bộ nhớ hơn nếu dữ liệu không bao giờ được hiển thị.

Answer 1

Bạn đang tìm kiếm để lưu trữ dữ liệu phân cấp trong một cơ sở dữ liệu.
Vấn đề là SQL không được trang bị để đối phó với loại dữ liệu này rất tốt.

Bạn có một số giải pháp, mỗi giải pháp có nhược điểm và ưu điểm của họ.
Dưới đây là một liên kết nếu bạn muốn đọc lên trên mỗi phương pháp:

http://www.sitepoint.com/hierarchical-data-database/
http://www.sitepoint.com/hierarchical-data-database-2/

yêu thích cá nhân của tôi là Modified Preorder Tree Traversal

Ở đây bạn lưu trữ bên trái và nút ngay trong cơ sở dữ liệu trong một cách truy cập rất trực quan, điều này làm cho việc chèn các nút chậm một chút, nhưng thu hồi dữ liệu cực nhanh.

Bạn có thể mã hóa logic của mình trong Delphi, nhưng tôi thích sử dụng các thủ tục được lưu trữ trong cơ sở dữ liệu được lựa chọn của tôi.
Bằng cách đó, logic của bạn trong Delphi vẫn đơn giản và nếu cơ sở dữ liệu thay đổi mã Delphi của bạn không phải. Nếu bạn muốn tôi có thể bao gồm mã SQL cho các thủ tục được lưu trữ, nhưng không phải ngay bây giờ, bởi vì mã đó không phải là trên máy tính xách tay tôi đã có với tôi bây giờ.

Answer 2

Không phải thanh lịch nhất nhưng đây là phương pháp tôi sử dụng để điền vào các cây của tôi.

Nó chỉ yêu cầu dữ liệu acess cho hai truy vấn đơn giản, và phần còn lại là tất cả được thực hiện phía khách hàng.

Nó sẽ tải hàng chục nghìn nút một cách dễ dàng. (Nhìn vào nó bây giờ, tôi có thể có thể nhận được ngay với chỉ một truy vấn - một chút của nó cũ!):

procedure TFrameComponentViewer.LoadComponentTree; 
var 
RootNodeData : PMasterComponent; 
CompQ,ParentQ : TMyQuery; 

procedure PopulateNodeData(Node: PVirtualNode;ComponentID : integer); 
var NodeData : PMasterComponent; 
begin 
    if CompQ.Locate('ComponentID',ComponentID,[loCaseInsensitive]) then 
    begin 
    NodeData := TreeComponents.GetNodeData(Node); 
    //Populate your desired TreeData 
    NodeData.ComponentID := CompQ.Fields[fldComponentID].AsInteger; 
    NodeData.ComponentCode := CompQ.Fields[fldComponentCode].AsString; 
    NodeData.ComponentType := CompQ.Fields[fldComponentType].AsInteger; 
    NodeData.IsPipeline := CompQ.Fields[fldComponentIsPipeline].AsBoolean; 
    NodeData.Description := CompQ.Fields[fldComponentDescription].AsString; 
    NodeData.StartKP := CompQ.Fields[fldComponentStartKP].AsFloat; 
    NodeData.EndKP := CompQ.Fields[fldComponentEndKP].AsFloat; 
    NodeData.Diameter := CompQ.Fields[fldComponentDiameter].AsFloat; 
    NodeData.WallThickness := CompQ.Fields[fldComponentWallThickness].AsFloat; 
    NodeData.CriticalSpanLength := CompQ.Fields[fldComponentCSL].AsFloat; 
    NodeData.Historical := CompQ.Fields[fldComponentHistorical].AsBoolean; 
    end; 
end; 

procedure AddNodesRecursive(ParentNode : PVirtualNode;ParentNodeID : Integer); 
var AddedNode : PVirtualNode; 
AddedNodeData : PMasterComponent; 
Children : Array of Integer; 
i : Integer; 
begin 
    try 
     ParentQ.Filtered := False; 
     ParentQ.Filter := 'Parent_ID = '+InttoStr(ParentNodeID); 
     ParentQ.Filtered := True; 
     ParentQ.First; 
     SetLength(Children,ParentQ.RecordCount); 
     for i:=0 to ParentQ.RecordCount-1 do 
     begin 
      Children[i] := ParentQ.Fields[0].AsInteger; 
      ParentQ.Next; 
     end; 
     for i:=0 to High(Children) do 
     begin 
      AddedNode := TreeComponents.AddChild(ParentNode); 
      AddedNodeData := TreeComponents.GetNodeData(AddedNode); 
      System.Initialize(AddedNodeData^); //initialize memory 
      PopulateNodeData(AddedNode,Children[i],CompQ); 
      AddNodesRecursive(AddedNode,AddedNodeData.ComponentID); 
     end; 
    finally 
    end; 
end; 

begin 
    TreeComponents.BeginUpdate; 
    treeComponents.Clear; 
    CompQ := TMyQuery.Create(nil); 
    ParentQ := TMyQuery.Create(nil); 
    try 
     CompQ.Connection := DataBaseline.BaseLineConnection; 
     CompQ.SQL.Add('SELECT * FROM Components'); 
     CompQ.Open; 
     ParentQ.Connection := DataBaseline.BaseLineConnection; 
     ParentQ.Close; 
     ParentQ.SQL.Clear; 
     ParentQ.SQL.Add('SELECT ComponentID,Parent_ID FROM Components ORDER BY OrderNo'); 
     ParentQ.Open; 
     RootNode := TreeComponents.AddChild(nil); 
     RootNodeData := TreeComponents.GetNodeData(RootNode); 
     System.Initialize(RootNodeData^); //initialize memory 
     RootNodeData.ComponentID := -1; 
     AddNodesRecursive(RootNode,-1); 
    finally 
    TreeComponents.EndUpdate; 
    TreeComponents.FullExpand; 
    CompQ.Close; 
    ParentQ.Close; 
    FreeandNil(CompQ); 
    FreeandNil(ParentQ); 
    end; 
end; 

Lưu ý: cột OrderBy là không bắt buộc, tôi yêu cầu nó như là cây của tôi là thứ tự cụ thể.

Vì vậy, DB có ba cột này, cộng với bất kỳ dữ liệu tùy bạn yêu cầu:

ID, ParentID (-1 cho không mẹ), OrderNo