روشهای ذخیره درخت در دیتابیس

[جواد ملاولی]

دوستان سلام.
از شما می خوام کمک کنید انواع روشهای دخیره سازی درخت در دیتابیس رو توضیح بدیم.

یک روش ساده اینه که یک فیلد داشته باشیم برای شماره گره و یک فیلد برای شماره پدر این گره که برای گره اول -که پدر نداره- مقدارش صفر میشه.

روشهای بعد به عهده دوستان اهل فن.

[جواد ملاولی]

اساتید اهل فن لطفاً کمک کنند.

[Saeed_m_Farid]

از شما می خوام کمک کنید انواع روشهای دخیره سازی درخت در دیتابیس رو توضیح بدیم.
سلام، دوست عزیز:
شما وقتی یه سوال می پرسید که اینقدر کلی هست و ربط چندانی به دلفی نداره، نباید انتظار داشته باشین سریع جواب بگیرید، سوال شما بیشتر مربوط میشه به طراحی الگوریتم تا دلفی!
سوالهایی که میتونه تو واضح شدن سوال شما در ارتباط با دلفی کمک کنه:


ساختار Tree شما چیه؟ فقط نود چپ و راست داره یا چند تا فرزند میتونه داشته باشه؟ پیاده سازی ساختاری که تو دلفی کردین، چیه؟
از یکی از کامپوننتهای خود دلفی استفاده کردین و میخواهید اون رو Export کنید؟
تا جایی که خودتون انجام دادین بفرمایید تا ما ادامه بدیم ..

در ساده ترین حالت و بدون اطلاع از ساختار شما، میشه یه همچین ساختاری برای یه جدول ساده درنظر گرفت، در حالتی که درخت شما تنها دارای دو فرزند چپ و راست باشه :
http://www.oreillynet.com/ruby/blog/images/ror/tree-structure.png

==============


A : ساده ترین جدول پیشنهادی برای درخت موردنظر
B : درخت مورد نظر
C : شکل مرتبط با treemap

==============
البته توجه کنید که این ساده ترین حالت هست، برای نمونه ای که مثلاً شما از دلفی استفاده می کنید و یه کلاس VCL دارید استفاده می کنید، بهترین راه حل به نظر من ذخیره درخت تو XML هست، با توجه به این که XML کاملاً این ساختارها رو ساپورت میکنه و همخوانی داره و همه هم اونو قبول دارن و راه حلهایی براش پیاده کرده (از جمله دلفی)، فرض کنید شما یه Treeview دارید و قصد ذخیره اون رو دارید، میتونید به صورت زیر عمل کنید، (یونیت های XMLDoc, XMLIntf موردنیاز هستند) :
procedure Tree2XML(tree: TTreeView);
var
tn : TTreeNode;
XMLDoc : TXMLDocument;
iNode : IXMLNode;

procedure ProcessTreeItem(
tn : TTreeNode;
iNode : IXMLNode);
var
cNode : IXMLNode;
begin
if (tn = nil) then Exit;
cNode := iNode.AddChild('item');
cNode.Attributes['text'] := tn.Text;
cNode.Attributes['imageIndex'] := tn.ImageIndex;
cNode.Attributes['stateIndex'] := tn.StateIndex;

//child nodes
tn := tn.getFirstChild;
while tn <> nil do
begin
ProcessTreeItem(tn, cNode);
tn := tn.getNextSibling;
end;
end; (*ProcessTreeItem*)
begin
XMLDoc := TXMLDocument.Create(nil);
XMLDoc.Active := True;
iNode := XMLDoc.AddChild('tree2xml');
iNode.Attributes['app'] := ParamStr(0);

tn := tree.TopItem;
while tn <> nil do
begin
ProcessTreeItem (tn, iNode);

tn := tn.getNextSibling;
end;

XMLDoc.SaveToFile(ChangeFileExt(ParamStr(0),'.XML' ));
FreeAndNil(XMLDoc);
end; (* Tree2XML *)


برای توضیحات مفصل تر (مثلاً بازگردندان XML به Treeview) میتونید به منبع این کد (http://delphi.about.com/library/weekly/aa101904a.htm) مراجعه کنید.
بعنوان یه راه حل در ارتباط بین SQL Server 2000 و 2005 و XML می تونید به لینک زیر مراجعه کنید (با توجه به اینکه -مثل سوال شما- هیچ ربطی به دلفی نداره!):
Tree utilities in SQL Server 2000 and 2005, and OLAP implementations (http://www.codeproject.com/KB/database/tree_olap.aspx)

[جواد ملاولی]

سلام. با تشکر از شما، این ساختاری که فرمودید برای وقتی که گره ها بیشتر از دو فرزند داشته باشن جواب نمی ده؟ اگه نمی ده چرا؟

[Saeed_m_Farid]

...این ساختاری که فرمودید برای وقتی که گره ها بیشتر از دو فرزند داشته باشن جواب نمی ده؟ اگه نمی ده چرا؟
شما حداقل یکی از سوالات من رو جواب بدید، تا ادامه بدیم ...
ضمناً من ساختاری ندادم! شما قرار بود ساختارتون رو بگید و بر حسب اون ما نحوه ذخیره تو دیتابیس رو بررسی کنیم.
اگه مثلاً شما یه B-Tree (همونی که اوراکل برای ایندکسینگ (http://mattfleming.com/node/192) ازش استفاده میکنه) یا هر ساختار سلسله مراتبی دیگه، داشته باشید، خود SQL Server 2008 یه دیتا تایپ built-in داره به نام hierarchyid (http://technet.microsoft.com/en-us/library/bb677290.aspx) برای ذخیره اطلاعات سلسله مراتبی، برای توضیح این نوع داده میتونید به لینکهای زیر مراجعه کنید (ولی فکر نمی کنم هنوز هم سوال شما ربطی به دلفی داشته باشه!!!) :


SQL Server 2008 - HierarchyID - Part I (http://blogs.msdn.com/manisblog/archive/2007/08/17/sql-server-2008-hierarchyid.aspx)
hierarchyid (Transact-SQL) (http://technet.microsoft.com/en-us/library/bb677290.aspx)

موفق باشید.

[جواد ملاولی]

دوست عزیز حق با شماست؛ سوال من خیلی ربطی به دلفی نداره. ولی از اونجایی که برنامه ام رو دارم با دلفی می نویسم، سوالم رو اینجا مطرح کردم. اما توضیح برنامه:
اول اینکه من از بانک اکسس استفاده می کنم. من در برنامه چند تا درخت دارم که
باید در دیتا بیس ذخیره شون کنم که لزوما درخت دودویی نیستن. برای این کار یک جدول Trees دارم و یه جدول Nodes. لطفا تصویر ضمیمه رو نگاه کنید.
یک نمونه از درختهایی که در برنامه می سازم ضمیمه کردم.
حالا سوال من و علت اینکه این تاپیک رو ایجاد کردم این بود که آیا ساختار بهتری برای ذخیره این درختها هست؟

[اوبالیت به بو]

روشي كه در پست اول گفتين مناسب هستش.
هر گره اي يه ID داره و يه Parent_ID و يه Level_ID يا همون سطح و شما سطح به سطح به صورت رديفي پيمايش مي كنيد و گره ها رو نشون مي ديد.

[spsgorgan]

جسارتاً من سوالی در مورد شمارش همون نود های مثال بالا داشتم . من با چه الگوریتمی می تونم تعداد نودهای سمت راست یا چپ گره پدر (A) رو شمارش کنم ؟

[behnam-s]

جسارتاً من سوالی در مورد شمارش همون نود های مثال بالا داشتم . من با چه الگوریتمی می تونم تعداد نودهای سمت راست یا چپ گره پدر (A) رو شمارش کنم ؟
سلام
برای نود ها سمت چپ می تونید یک پیمایش به صورت infix انجام بدین تا وقتی که به گره مورد نظر برسین.
برای سمت راستی ها هم میشه تعداد کل زیر شاخه های فرزند سمت راست رو پیدا کنید بعد به اضافه 1 کنید

[spsgorgan]

تا وقتی که به گره مورد نظر برسین.
بهنام جان
من نمیخوام به گره خاصی برسم فقط میخوام بگه سمت چپ این تعداد نود و سمت راست هم این تعداد نود . آیا فرمول خاصی میتونید پیشنهاد بفرمایید ؟

[behnam-s]

بهنام جان
من نمیخوام به گره خاصی برسم فقط میخوام بگه سمت چپ این تعداد نود و سمت راست هم این تعداد نود . آیا فرمول خاصی میتونید پیشنهاد بفرمایید ؟
من متوجه ام . ولی برای شمارش گره ها راهی جز پیمایش نیست.
شما یک متغیر به این حالت تعریف می کنید int count=0. و در پیمایش ، در هر گره ، count=count+1
می کنید تا به گره A برسید.

[spsgorgan]

2 نکته پیمان جان :
1 : "تا به گره A برسید" . این گره A باید دارای چه مشخصاتی باشه که بفهمیم رسیدیم
2 : میشه یک نمونه کد برای پیمایش بفرمایید . من با زبان PHP مینویسم اما به زبان c یا الگوریتم هم باشه ممنون میشم

[behnam-s]

2 نکته پیمان جان :اگه منظور منم ، بهنام هستم

1 : "تا به گره A برسید" . این گره A باید دارای چه مشخصاتی باشه که بفهمیم رسیدیمid ,عکس صفحه قبل رو ببینید ، واضحه

در مورد پیمایش 36763

[spsgorgan]

بهنام امکانش هست یک مثال عملی از پیمایش inorder بفرمایید (ترجیها C++ یا PHP)

با سپاس