كيف كنت تمثل hashtable في مخطط قاعدة البيانات?

Question

إذا كنت تحاول إنشاء كائن المجال في مخطط قاعدة البيانات في التعليمات البرمجية الخاصة بك قال كائن المجال لديه hashtable/قائمة الأعضاء, مثل ذلك:

public class SpaceQuadrant : PersistentObject
{

    public SpaceQuadrant()
    {
    }

    public virtual Dictionary<SpaceCoordinate, SpaceObject> Space
    {
        get;
        set;
    }
}

القاموس هو مجرد hashtable/قائمة الخرائط كائن مفاتيح قيمة مفاتيح, لقد جئت مع عدة طرق للقيام بذلك ، وخلق مختلف الانضمام إلى الجداول أو تقنيات التحميل ولكن كلها سيئة من حيث الحصول على تلك O(1) وقت الوصول التي تحصل في hashtable.

كيف كنت تمثل SpaceQuadrant, SpaceCoordinate و الفضاء الكائن في مخطط قاعدة البيانات?بسيطة مخطط رمز الوصف أن يكون لطيفا ، ie.

table SpaceQuadrant
{
    ID int not null primary key,
    EntryName varchar(255) not null,
    SpaceQuadrantJoinTableId int not null
                 foreign key references ...anothertable...
}

ولكن أي الأفكار في كل ما من شأنه أن يكون لطيف وكذلك شكرا على القراءة!

مزيد من المعلومات:

شكرا على الاجابات الصحيحة بالفعل ، لقد منزوع الدسم فقط لهم و لا تريد أن تأخذ بعض الوقت في التفكير في كل قبل أن أرد.

إذا كنت تعتقد أن هناك طريقة أفضل لتحديد هذه الفئات, ثم بكل الوسائل تظهر لي على سبيل المثال ، أي لغة مريحة الخاص بك هو بارد

Answer 1

أولا، الدعم المخصص للبيانات المتعلقة بالمواقع الجغرافية موجود في العديد من قواعد البيانات - خوارزميات مختلفة يمكن استخدامها (نسخة المكاني من B-شجرة يوجد على سبيل المثال)، وتقديم الدعم لقربها بالبحث ربما سيكون موجودا

.

ومنذ لديك جدول تجزئة مختلفة لكل SpaceQuadrant، وكنت بحاجة إلى شيء مثل (تحريره من آخر S.Lott ل):

table Space {
    SpaceCoordinate,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is (by ID)
    Primary Key(SpaceCoordinate, Quadrant)
}

وهذا هو قاموس (SpaceCoordinate, Quadrant) -> SpaceObjectId.

و=====

والآن، حول O الخاص بك (1) قلق الأداء، وهناك الكثير من الأسباب التي تجعل انها تعالج خطأ.

ويمكنك استخدامها في مؤشر التجزئة العديد من DB للجداول المعتمدة على الذاكرة، وشخص ما قال لك. ولكن إذا كنت بحاجة إلى التخزين الثابتة، وكنت بحاجة إلى تحديث جدولين (الذاكرة واحد واحد مستمر) بدلا من واحدة (إذا لم يكن هناك دعم المدمج في لهذا). لاكتشاف ما إذا كان ذلك يستحق، كنت بحاجة لقياس على البيانات الفعلية (مع أحجام البيانات الفعلية).

وأيضا، مما أدى الى الجدول في الذاكرة يمكن أن يكون لها آثار أسوأ.

وإذا كان شيء من أي وقت مضى يحصل تبادلت، كنت ميتا - إذا كنت قد استخدمت (أي مؤشر يستند إلى قرص العادي) B-شجرة، فإن الخوارزميات والتقليل من حاجة I / O. وإلا، فإن كل من DBMS استخدام الجداول التجزئة والاعتماد على مبادلة، بدلا من B-الأشجار. يمكنك محاولة لاستباق ما إذا كنت سوف يصلح في الذاكرة، ولكن ...

وعلاوة على ذلك، B-الأشجار ليست O (1) لكنها O (log_512 (N))، أو أشياء من هذا القبيل (وأنا أعلم أن ينهار لO (تسجيل N)، ولكن تحمل لي على هذا). كنت بحاجة (2 ^ 9) ^ 4 = 2 ^ 36 = 64GiB لذلك أن يكون 4، وإذا كان لديك الكثير من البيانات لذلك كنت بحاجة إلى خادم الحديد كبيرة على أي حال لذلك لتناسب في الذاكرة. لذلك، انها تقريبا O (1)، وعوامل ثابتة هي ما يهم في الواقع.
سمعت عن المنخفض مقارب التعقيد، والخوارزميات كبير-ثابت عامل، التي من شأنها أن تكون أسرع من تلك بسيطة فقط على أحجام البيانات غير عملية؟

وأخيرا، وأعتقد أن الكتاب DB أكثر ذكاء من لي ولكم. لا سيما في ظل طبيعة التعريفي للSQL، وهذا الطريق الأمثل جهة ليست ستعمل الأجر. إذا كان مؤشر يناسب في الذاكرة، وأنا أعتقد أنها يمكن أن تختار لبناء واستخدام إصدار جدول هاش من مؤشر القرص، حسب الحاجة، إذا كان يستحق ذلك. التحقيق في مستندات الخاصة بك لذلك.

ولكن خلاصة القول هي أنه، والتحسين من السابق لأوانه هو الشر، وخاصة عندما يكون من هذا النوع (تحسينات غريبة نحن نفكر في منطقتنا، في مقابل كما أمثل SQL القياسية)، مع وجود اللغة التقريرية.

Answer 2

والعلاقات لا يتم تجزئة الجداول؛ هم مجموعات.

وأود أن لا تنظيم قاعدة البيانات باستخدام إحداثيات كمفتاح. ماذا لو كان موقع تغييرات الكائن؟ بدلا من ذلك، وأنا ربما علاج الإحداثيات ك <م> سمات كائن.

وأيضا، وأفترض أن هناك عدد محدد من أبعاد، على سبيل المثال، ثلاثة. إذا كان الأمر كذلك، ثم يمكنك تخزين هذه سمات كائن في الأعمدة الثابتة:

CREATE TABLE SpaceQuadrant (
  quadrant_id INT NOT NULL PRIMARY KEY,
  quadrant_name VARCHAR(20)
  -- other attributes
);

CREATE TABLE SpaceObject (
  object_id INT NOT NULL PRIMARY KEY,
  x NUMERIC(9,2) NOT NULL,
  y NUMERIC(9,2) NOT NULL
  z NUMERIC(9,2) NOT NULL,
  object_name VARCHAR(20) NOT NULL,
  -- other attributes
  quadrant_id INT NOT NULL,
  FOREIGN KEY (quadrant_id) REFERENCES SpaceQuadrant(quadrant_id)
);

في الدرجة وجوه المنحى، فإنه ليس من الواضح لماذا الأشياء الخاصة بك هي في القاموس. أذكر لكم الوصول إليها في O (1) الوقت، ولكن لماذا كنت تفعل ذلك عن طريق تنسيق؟

إذا كنت تستخدم ذلك لتحسين العثور على الأشياء التي هي بالقرب من نقطة معينة (سفينة الفضاء اللاعب، على سبيل المثال)، هل يمكن أيضا بناء في استعلام SQL الخاصة بك التي بملء هذا SpaceQuadrant حساب المسافة كل كائن من هذه النقطة نظرا ، وفرز النتائج وفقا لعن بعد.

وأنا لا أعرف ما يكفي عن البرنامج لمعرفة ما إذا كانت هذه الاقتراحات هي ذات الصلة. ولكن هل هم على الأقل يجعلك تفكر في طرق مختلفة لتنظيم البيانات؟

Answer 3

في أبسط الحالات ، القاموس الرئيسية التي من شأنها أن خريطة المفتاح الأساسي من الجدول بحيث عند تحديد القيم الرئيسية ، يمكنك على الفور العثور على مطابقة البيانات عبر بحث بسيطة.

في هذه الحالة, كنت في حاجة الى طاولة SpaceQuadrant مع أي (مفردة) من الصفات التي تصف أو تميز الفضاء رباعي.على SpaceQuadrant الجدول سيكون المفتاح الأساسي ، وربما ولدت ID, ربما الطبيعية القيمة.Hashtable وعندئذ تتكون من طاولة مع قيمة المفتاح الأساسي عبر الرجوع SpaceQuadrant مع الموقف (أ SpaceCoordinate) و سمات رباعي وتنسيق.

الآن, إذا كان لديك الموسعة DBMS ، يمكنك تحديد نوع معرف من قبل المستخدم عن SpaceCoordinate;إذا تعذر ذلك, يمكنك استخدام ثلاثة من أعمدة - x ، y ، z أو r ، ثيتا ، رو ، على سبيل المثال - إلى تمثل موقف (SpaceCoordinate).

وبصفة عامة ، فإن هيكل أنا تصف مماثلة تماما بيل Karwin ؛ المفتاح (لا يقصد التورية حتى بعد أن تم إعادة قراءة الرسالة) الفرق هو أنه على ما يرام تماما في كتابي أن يكون موقف كجزء من المفتاح الأساسي من دون تنسيق الجدول إذا كنت متأكدا من أن هذا هو أفضل وسيلة لتنظيم ذلك.قد يكون لديك أيضا كائن معرف العمود الذي هو مرشح بديل الرئيسية.بدلا من ذلك, إذا كانت الأشياء لها وجود مستقل عن الفضاء رباعي يحدث أن تكون في هذه اللحظة (أو يمكن أن توجد في مواقف متعددة - لأنها ليست نقطة بل هي المحطات الفضائية أو شيء), ثم قد يكون لديك SpaceObject في جدول منفصل.ما هو أفضل يعتمد على المعلومات التي لم تكن متاحة لنا.

يجب أن يكون على بينة من القيود المفروضة على استخدام SpaceCoordinate كجزء من المفتاح الأساسي:

• أي كائنين يمكن أن تشغل نفس الموقف (يسمى هذا الاصطدام في جدول تجزئة ، وكذلك في 3D الفضاء) ،
• إذا تغير موقف ، ثم يجب عليك تحديث البيانات الرئيسية ، والتي هي أكثر تكلفة من تحديث غير البيانات الرئيسية ،
• القرب عمليات البحث سوف يكون من الصعب الدقيق عمليات البحث من السهل بما فيه الكفاية.

نفس الشيء ينطبق على القاموس الخاص بك في الذاكرة ؛ إذا قمت بتغيير الإحداثيات لديك لإزالة سجل من الموقع القديم ووضعه في الموقع الجديد في القاموس (أو لغة ما وراء الكواليس).

Answer 4

ومعجم <م> هو على الطاولة. تجزئة هي مسألة ما يستخدم نوع من المؤشر. تفترض معظم RDBMS أن الجداول كبيرة والمزدحمة بالسكان، مما يجعل مؤشر المجزأة غير مناسبة.

table SpaceQuadrant { 
    ID Primary Key,
    -- whatever other attributes are relevant
}

table Space {
    SpaceCoordinate Primary Key,
    Quadrant Foreign Key SpaceQuadrant(ID),
    SpaceObject -- whatever the object is
}

والأجسام الفضائية لديك لديها مراجع FK إلى ربع الدائرة في انهم التي تقع.

واعتمادا على RDBMS الخاص بك، فإنك قد تكون قادرة على العثور على مؤشر القائم على التجزئة التي يحصل لك أداء كنت تأمل. على سبيل المثال الخلية، وذلك باستخدام محرك التخزين هيب يدعم مؤشرات HASH.