ibash.org.ru - Новый цитатник Рунета

Цитаты: По дате По рейтингу Случайно Добавить Поиск RSS

Форум: [My]SQL. Какой номер листочка, если сказано его имя и на какой он ветке. 1 > [RSS]

Форум: Вход Регистрация Участники Поиск RSS
Shock
29.05.2009 - 22:50
Допустим, у нас есть форум по адресу http://forum.lh . Но он имеет чуть необычную структуру. В нем может быть неограниченное количество форумов с неограниченной вложенностью. При этом, обращение к каждому отдельному из них идёт по полному пути...
Shock
#1 - 29.05.2009 - 22:50
Задание следующее. Допустим, у нас есть форум по адресу http://forum.lh . Но он имеет чуть необычную структуру.
В нем может быть неограниченное количество форумов с неограниченной вложенностью.
Структуру таблицы Forums представим следующей: [ID, Title, ParentID]
Для облегчения задания предположим, что Title у нас может иметь только латинские буквы(минимум одна) и цифры и быть не больше 64 символов. ParentID - это айди форума-родителя, или NULL
Структура таблицы Topics: [ID, Title, ForumID]
Теперь суть задачи на примере:

forum.lh/first/second/third/HelloWorld.html
Такой адрес должен открывать тему "HelloWorld" в форуме с названием "third", который лежит в форуме с названием "second", который лежит в форуме с названием "first".

Вопрос: как узнать ID темы, которую нам надо отобразить, если:
Тем с таким названием может быть несколько, но только в разных форумах! Например:
forum.lh/first/second/third/HelloWorld.html
forum.lh/first/fourth/fifth/HelloWorld.html
forum.lh/first/second/HelloWorld.html
forum.lh/first/HelloWorld.html
В данном случае это все реальные и, при этом РАЗНЫЕ темы.
Более того, могут дублироватся названия форумов, но не в одном форуме. То есть
forum.lh/second/second/
forum.lh/second/first/
forum.lh/first/second/
forum.lh/first/first/second/first/
Это все вполне валидные пути РАЗНЫХ форумов.
Далее. Допустим, вложенность может быть очень большой. Например, 64 форума.

Повторяю вопрос и раскрываю чуть проблемы:

* Как узнать ID темы, которую нам надо отобразить.

Ситуация:
1. У нас есть только её название, которое НЕ УНИКАЛЬНО и полный путь к ней.
2. О каждом участке пути мы только знаем его неуникальное название и полный путь к нему
3. В пути может быть до 64 делений.
4. У нас есть высоконагруженная система, в которой количество запросов должно быть сведено к минимуму. Желательно, общее количество запросов(включая не только анализ пути) - не больше 15.

Решения, о которых я знаю:
1. Решение "вЛоб"
Получаем айди первой секции простым запросом к базе:
${FirstID} = SELECT `ID` FROM `Forums` WHERE `Title` = `${Title}` AND `ParentID` IS NULL
Получаем айди второй секции простым запросом к базе:
${SecondID} = SELECT `ID` FROM `Forums` WHERE `Title` = `${Title}` AND `ParentID` = '${FirstID}'
И так пока не дойдем до последней секции, то есть темы.
Решение не подходит. Причина: до 65 запросов только на получение темы.

2. Materialized Path
У нас в базе хранятся полные пути к каждому форуму. Допустим, для этого у нас есть отдельная таблица "ForumsPathes" со структурой [ForumID, FullPath]. Пример содержимого:
1 | first
2 | first/second
3 | second
4 | third
5 | first/second/third
Решение нежелательно. Причины:
1. Поле "FullPath" должно быть индексным varchar длинной (64*64+63) = 4159 символов. По этому полю будет регулярный поиск. Увеличение разрешенной длины названия темы/разрешенной глубины пропорционально увеличит длину поля. Решение, в общем то, ничего такое, но... "#1071 - Specified key was too long; max key length is 1000 bytes". То есть максимально-разрешенная длина в данном случае всего 1000 символов - недостаточно.

Более того, решение не должно быть слишком тяжелым для понимания (желательно, левому человеку посмотреть на код и сразу понять, как оно должно работать) и не перегружено Join'ами (скажем, максимум - 4-8 на запрос).

Пока очень застопорился на этом. Если кто сможет помочь описанием алгоритма решения этой задачи - буду рад. :)
Кавайный Няшг
#2 - 30.05.2009 - 00:03
Решение "в лоб":
вычисляешь хеш по полному пути. Результат хеша -- ID конечного форума. Переходишь туда.
Ня?
(или я что-то не понял?)
Shock
#3 - 30.05.2009 - 00:05
хм... интересно... то есть то, что я записывал бы в "FullPath", но не все, а его хеш... Мне нравится...
Кавайный Няшг
#4 - 30.05.2009 - 00:08
^_^
Рад помочь благому делу!
ihumster
#5 - 30.05.2009 - 00:46
Няшг, читаешь мои мысли))
Только надо подсчитать максимально возможное количество тем (то вдруг айдишников на темы не хватит).
Shock
#6 - 30.05.2009 - 00:58
ну сейчас у меня айдишников на темы int(11), то есть, если включить беззнаковость, то можно будет создать 4294967295 тем. Надеюсь, этого хватит :))) Хеш - идея отличная. Я так подумал, она решает множество моих проблем, спасибо :) Даже несмотря на коллизии
Кавайный Няшг
#7 - 30.05.2009 - 01:02
#5
> Няшг, читаешь мои мысли))
Ага, щаз-з... (((=

"#4 - 30.05.2009 - 00:08
#5 - 30.05.2009 - 00:46"
Это Ты _читаешь_ мои... (-;

> Только надо подсчитать максимально возможное количество тем (то вдруг айдишников на темы не хватит).
101! Сколько ж тем должно быть, чтобы хеш ошибся? Неужели весь интернет уважаемый Shock-сама собирается проиндексировать у себя на форуме? эээ... Shock-сама?? о_О

P.S.
Топикстартер-сан, а полнотекстовый поиск будет? *мечтательно жмурюсь* Или токмо тематический/временной?
+Если не сложно, опубликуйте намечаемый интерфейс.
Кавайный Няшг
#8 - 30.05.2009 - 01:07
Эммм...
Я говорил об пространстве UID (хеш-ключе).
Пространство ID, конечно, меньше, и в 4 байта, полагаю, влезет. ;-)
Нужно только выставить таблицу соответствия ID(пересчётный)-UID(хешевой).
Shock
#9 - 30.05.2009 - 01:18
http://www.az-design.ru/index.shtml?Support&DataBase&Hash-PrimaryIndex
> Все бы было хорошо, но коллизии начались при размере таблицы около 300000 записей.
А 300000 - это, извините, мелочь та ещё :)

> Если не сложно, опубликуйте намечаемый интерфейс.
Ээмс... http://freecr.ru/ - не?

Полнотекстового не будет, ибо использую InnoDB. Почему не MyISAM ? Нужны транзакции. Зачем? Есть достаточно тяжёлые инсерты, которые должны обязательно быть выполнены только вместе. Зачем? Чтобы разгрузить более часто-выполняемые селекты. Какая альтернатива будет? Достаточно простой поиск по ключевым словам в сообщениях, времени, названиям тем. Возможно, в будущем сделаю более продвинутую систему поиска.
Temcha
#10 - 30.05.2009 - 01:30
Я только не пойму, Шок, почему ты завязался на имена топиков?
Ну, присвоил топику при создании уникальный ID, и пути строишь исходя из него. Ну, ессно, хранишь табличку соответствия ID-название, это и ежу понятно.
Или я чет не понял?
Кавайный Няшг
#11 - 30.05.2009 - 01:32
#9
> > Все бы было хорошо, но коллизии начались при размере таблицы около 300000 записей.
>=128-битовый хеш разве не вариант? Всё равно ж UID нужно получить, а соответствие их с ID -- дело отдельной таблицы, десу.

> Ээмс... http://freecr.ru/ - не?
>_< Ну, эээ... я имел в виду нечто вроде man shell. Не тот, заголовок которого сейчас по help вызывается, а тот, который ожидается.

> Полнотекстового не будет
Если всё же надумаете, позовите меня... ^_^
Кавайный Няшг
#12 - 30.05.2009 - 01:40
#10, Shock чурается потенциальных 64 переходов для каждого из тысячей-тысяч юзверей. (=
+Неясно, как у него структуры хранятся. Из описанного выходит, что форумы связаны "обратной" зависимостью, но вот из корня (в принципе, в зависимости от построенной БД) получать такой маршрут не всегда возможно. Хотя, по мне такая гипотетическая ситуация выглядит немного странноватой (как же ls получать? Можно, конечно, организовать промежуточное избыточное хеширование, и по вычету определять всевозможные подфорумы, но по-мне, малость извращение. Так что, скорее всего, каждый из форумов -- таблица подфорумов/топиков, а проблема полностью описана в первой строке данного сообщения (= ).
Shock
#13 - 30.05.2009 - 01:58
> Так что, скорее всего, каждый из форумов -- таблица подфорумов/топиков, а проблема полностью описана в первой строке данного сообщения
Наверное, так и есть :) Пока карты раскрывать не буду.

> Ну, присвоил топику при создании уникальный ID, и пути строишь исходя из него.
Так, например, на АйБаше. Да и на всех остальных форумах. Это лёгкий, очевидный вариант, который сейчас и используется. Я сделаю более православно :) Это к пункту 1. Пока всех карт раскрывать не буду :) Надеюсь, в ближайшие несколько дней мир увидит заготовки данного движка.

> 128-битовый хеш разве не вариант?
md5 и есть 128-битовый. Я думаю, его сделать хотя-бы 512-битовым, плюс (возможно) проверять по уровню и названию форума. Тогда это обеспечит достаточный шанс уникальности. Хеши будут хранится от полного адреса, например md5(first/first/second/first/). При количестве топиков более 100000 возможны колизии

> как же ls получать?
В общем то, в этом и был вопрос. Ты мне на него дал ответ, спасибо :)
Temcha
#14 - 30.05.2009 - 02:01
Если уж сильно хочется осмысленные имена в путях, то, думаю, их стоит ограничить 8-10 знаками. Заставить при создании топика вводить алиас, или тупо транслитерировать первые 10 непробельных символов.
Прикинь, это чтобы добраться до пресловутого топика, юзеру надо будет ввесть те самые 4159 символов. )
У меня в институте рефераты короче были. )
И фулпас 640 знаков у тебя влезет.
Хотя с хешем красивее. )
Shock
#15 - 30.05.2009 - 02:07
> Ну, эээ... я имел в виду нечто вроде man shell
То есть команды, которые будут?
Ну, честно говоря, мало что поменяется сравнительно с текущей версией. Естественно, post и topic заменятся на echo "Smth" > URL. Добавятся греп, сорт, хед, тейл, существенно переработан анализатор запроса - более правильный разбор комманды, будет конкатенация команд через "&&". Будет экранизация, более правильный анализатор адреса. (например, "/topic", "../topic", "./topic", "topic") теперь все постараюсь заставить работать. Полностью перенёс логику отображения на сторону клиента. Создан специальный язык бб-разметки манов. Теперь наконец будут нормальные маны.
Это из того, что вспомнил. Многое по ночи забыл :)
Большинство вышесказанного либо уже реализованно, либо почти реализовано, либо детально продуман алгоритм.
Shock
#16 - 30.05.2009 - 02:10
И да, можно заметить я ничего не сказал про автодополнение по табу. Постараюсь сделать, ничего не обещаю. Но если и сделаю - будет достаточно примитивный - автодополнение только команд и адресов.

Temcha, ну в Линуксе в названии папки может быть и 255 символов, как то живем ведь ;) Даже если так случится, что автодополнение я не реализую (надеюсь, это не случится) - будет удобное средство для быстрого набора адреса.
Temcha
#17 - 30.05.2009 - 02:12
Все чудесатее и чудесатее! (с)
Кавайный Няшг
#18 - 30.05.2009 - 02:13
#13.3
Шозанах? 128 битов не обеспечит 32 битам уникальности по первичным коллизиям? Не верю! Дважды не верю!
Коллизий будешь избегать, добавляя свою секретную "соль". Именно для этого и требуется разделение UID и ID, иначе нах? Юзер не должен знать UID, чтобы не обратить хеш.
Temcha
#19 - 30.05.2009 - 02:13
Кстате, мож посоветуете (да еще и со ссылкой) книгу по пыху аля "сайт с нуля для полных чайников"?
Shock
#20 - 30.05.2009 - 02:19
#18 > http://ru.wikipedia.org/wiki/Парадокс_дней_рождения
#19 > http://ua.php.net/manual/ru/index.php
Темча, не сочти за издевательство, честное слово - ни единой книжки по пыху я так и не прочитал. Мой путь обучения пролегал приблизительно так:
1. Вслепую полгода ставлю моды на phpbb2
2. Делаю простенький показыватель картинок из папки на 10 строчек
3. Делаю таблицу, которая генерируется из базы на 50 строчек.
4. ???? И так дальше по нарастающей. Если будут вопросы - с удовольствием отвечу например, в Jabbere (смотри профиль)
Temcha
#21 - 30.05.2009 - 02:22
))) В любом начинании нужна точка входа. Книга - не самая хреновая точка. )
Тем более, что просвещаться можно в непродуктивное время в трамвае. )
Shock
#22 - 30.05.2009 - 02:24
я не говорю, что книга - это плохо. просто посоветовать не могу, ибо ни одной не читал :)))
Кавайный Няшг
#23 - 30.05.2009 - 02:25
#19, не забывай, на каком ты форуме!
А значит:
1) Сначала тебе насоветуют Олифера и Ко (по сетям);
2) Затем -- Таненбаума (по сетям и первичной архитектуре ПК);
3) Далее -- посоветуют скачать ассемблер и научиться ему по манам с wasm-а;
4) Потом -- книги по инет-протоколам;
5) После -- на 30-60 кб обосрут пхп и всех, кто на нём кодит;
7) Вспомнят суперкомпьютеры и перфокарты, а также то, как хорошо обходились без всяких инетов, и особенностях апранета (со слов разработчиков, которые сидят на сием форуме);
6) Впарят десяток книженций по Питону, Лиспу, Прологу и Жабе;
7) Повторят пункт (5) 2-3 раза;
8) Начнут обсуждать gentoo.
Кавайный Няшг
#24 - 30.05.2009 - 02:27
#20, я в курсе.
И всё равно, 96 бит / 2 = 48 бит стойкости для коллизии второго рода.
Кавайный Няшг
#25 - 30.05.2009 - 02:38
Охренеть. Половина шестого уже, а здесь активно ведутся споры...
Линуксоиды определённо подвержены лунной активности.
А глаза красные у гентушников (как самых адаптированных), вестимо, чтобы зреть в ИК-диапазоне.
Ночами они выходят на улицы... и пересобирают мир... но человечеству ничего об этом не ведомо, оно спит... и каждый сон -- это лишь период между Рождением и Смертью Яйца Брахмы, т.е. рекомпиляцией и отладкой всего world-а...
Арс
#26 - 30.05.2009 - 02:44
Temcha, php примитивен на самом деле, я со своим сяшно/паскальным образованием без труда читаю практически любой пых-код. Порог вхождения еще очень низок за счет большого коммунити и кучи примеров. Набери в поисковике скрипты php. Питон интереснее, да. Но и осилить его сложнее. Быдлокодить с набегу, налету, методом копипаста и разбираться по ходу дела там сложнее.

Зы: книжек по программирования также не читал. Только исходники.
Кавайный Няшг
#27 - 30.05.2009 - 02:54
Согласно индуистской космологии Пуран существует вечный цикл попеременной сборки и пересборки вселенной. Продолжительность существования вселенной составляется около 4,32 млрд лет (один день Брахмы). По прошествии дня Брахмы вселенная разрушается элементами пива и красноглазия, после чего Брахма отдыхает в течение одной ночи, длящейся столь же долго, как день, а затем вновь творит вселенную (собирает мир). «Жизнь» Брахмы длится 100 лет (311 040 000 000 000 лет по человеческим меркам), после чего он «умирает» и спустя ещё сто лет Брахмы «рождается» вновь. По верованиям индуистов, с момента рождения последнего Брахмы прошёл 51 год Брахмы. Так что всего через 49 Брахма-лет (152 409 600 000 000 человеческих лет) gentoo будет полностью допилен.

// если не по теме, простите. Сознание рассссслаивается... поставить Ооо на апды, что-ли... высплюсь хоть...

#26, Арс, попробуй Malbolge так выучить. Я не смог. (= Хотя старался.
ihumster
#28 - 30.05.2009 - 09:41
#12, списки списков! Ура!!!
ihumster
#29 - 30.05.2009 - 09:43
или всё же таблица, ибо поиск быстрее..
К списку вопросовСтраницы: 1 >
Быстрый ответ
Имя:      Пароль:    
Текст сообщения:
«ibash.org.ru — Новый цитатник Рунета» Почта вебмастера: imail@ibash.org.ru