تعقيد الوقت/تحليل أداء MySQL

Question

إعداد (MySQL):

create table inRelation(
    party1 integer unsigned NOT NULL,
    party2 integer unsigned NOT NULL,
    unique (party1,party2)
);

insert into inRelation(party1,party2) values(1,2),(1,3),(2,3),(1,4),(2,5),(3,5),(1,6),(1,7),(2,7),(5,7);

mysql> select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+--------+--------+--------+--------+--------+--------+
| party1 | party2 | party1 | party2 | party1 | party2 |
+--------+--------+--------+--------+--------+--------+
|      1 |      2 |      2 |      5 |      5 |      7 |
|      1 |      3 |      3 |      5 |      5 |      7 |
+--------+--------+--------+--------+--------+--------+
2 rows in set (0.00 sec)

mysql> explain select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
| id | select_type | table | type   | possible_keys | key    | key_len | ref                 | rows | Extra       |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
|  1 | SIMPLE      | b     | index  | party1        | party1 | 8       | NULL                |   10 | Using index |
|  1 | SIMPLE      | a     | eq_ref | party1        | party1 | 8       | const,news.b.party1 |    1 | Using index |
|  1 | SIMPLE      | c     | eq_ref | party1        | party1 | 8       | news.b.party2,const |    1 | Using index |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+

هذا حل BFS لمشاركتي السابقة:

التحدي ، كيفية تنفيذ خوارزمية لستة درجة من الانفصال؟

ولكن ما هو تعقيد ذلك؟ لنفترض أن هناك تماما n السجلات.

Answer 1

على افتراض أن هناك رؤوس ن وحواف ه. لكل جدول يمكن أن يكون هناك انضمام بين كل زوج من القمم ويحتاج إلى التحقق من جميع القمم للمساواة. لذلك سيكون أداء حالة أسوأ O (| V | + | E |)

محدث: إذا كنت تفكر في MySQL ، فهناك الكثير من الأشياء التي تؤثر على التعقيد ، إذا كان لديك فهرس المفتاح الأساسي في الحقل ، فسيتم استخدام فهرس B-Tree. إذا كان فهرسًا عاديًا غير مستقر ، فسيتم استخدام مؤشر التجزئة. هناك تكاليف مختلفة لكل من هياكل البيانات هذه.

من سؤالك الآخر ، أرى أن هذا هو متطلباتك 1. احسب المسار من userx إلى USERY 2. بالنسبة إلى userx ، احسب جميع المستخدمين الذين لا يتجاوزون 3 خطوات.

لأول مرة ، أفضل شيء هو تطبيق خوارزمية Djikstra وإنشاء جدول في Java ثم تحديثه في الجدول. لاحظ أنه ، إضافة كل عقدة جديدة ، يحتاج إلى معالجة كاملة.

سيكون الحل الآخر لهذا هو استخدام SQL المتكرر الذي تم تقديمه في SQL 1999 Standard لإنشاء طريقة عرض تحتوي على المسار من userx إلى USERY. اسمحوا لي أن أعرف إذا كنت بحاجة إلى بعض المراجع للاستعلامات العودية.

بالنسبة للثاني ، فإن الاستعلام الذي كتبته يعمل بشكل مثالي.