BTREE ומחרוזות

[ניר טייב]

BTREE ומחרוזות

למערכת מאמרים שאני בונה (מערכת ווב) אין אפשרות לשימוש בDB. לכן חשבתי לאחסן את התכנים בתוך קבצי XML (קובץ XML לכל מאמר) ואז לאנדקס אותם. כיוון שאני יודע ש-MySQL משתמש ב-B-Tree עבור האינדוקס חשבתי שאולי גם אני אשתמש ב-B-Tree. אז התחלתי לקרוא בויקיפדיה אבל נתקלתי במס' קשיים: 1. שאני מכניס את המאמר אני צריך לפצל אותו לכמה Nodeים? או להשאיר אותו בתור Node אחד גדול? 2. נאמר לי שעליי להשתמש ב-strcmp כדי לקבוע את מקום ההשמה ב-Insertion אבל דבר אחד לא הבנתי ב-strcmp, איך מחרוזת נקבעת שהיא גדולה/קטנה יותר ממחרוזת אחרת? 3. איך יתבצע אינדוקס טוב אם המאמרים בודאות יהיו שונים בתוכנם ? תודה

 

[ניר טייב]

האינדוקס הוא בשביל חיפוש

לא בשביל שליפה (עבור שליפה אני משתמש במס' סידורי עבור קבצי ה-XML).

 

[IsraeliSecretToilets]

יש מבני נתונים יעודיים למחרוזות

יש מבנה קלאסי וידוע בשם hash table, וכן הוא מצויין גם בתור אינדקס למסד נתונים. אם השאילתות על מסד הנתונים הן גם range queries, כלומר "תביא את כל המחרוזות שלפי סדר לקסיקוגרפי בין X לבין Y" יש מבני נתונים אחרים טובים יותר, כמו לדוגמא ternary search tree.

 

[IsraeliSecretToilets]

וכמובן,

אם האינדקס זה משהו שבונים לעיתי נדירות תמיד אפשר לשמור פשוט רשימה ממויינת של מחרוזות. חיפוש ברשימה ממויינת של מחרוזות הוא (O(logn + k כאשר k הוא אורך המחרוזת המבוקשת ו-n היא כמות המחרוזות. זה אלגוריתם די דומה לחיפוש בינארי.

 

[ניר טייב]

מדובר במערכת שמתוכננת להתעדכן

מס' פעמים ביום (בעיקר הוספה של תכנים).

 

[ניר טייב]

ואם הכיוון הוא שאילתות Like ?

 

[IsraeliSecretToilets]

במקרה כזה, מן הסתם,

עדיף מבני נתונים כמו ternary search tree.