Re: Nested Sets vs. Nested Intervals

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>
Date: 19 Nov 2005 20:16:55 -0800
Message-ID: <1132460215.640595.152790_at_o13g2000cwo.googlegroups.com>

asdf wrote:
> CREATE TABLE `directory` (
> `id` int(6) unsigned NOT NULL auto_increment,
> `name` varchar(100) NOT NULL,
> `a11` int(8) unsigned NOT NULL,
> `a12` int(8) unsigned NOT NULL,
> `a21` int(8) unsigned NOT NULL,
> `a22` int(8) unsigned NOT NULL,
> PRIMARY KEY (`id`),
> KEY `name` (`name`,`a11`,`a12`,`a21`,`a22`)
> ) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;

(a11, a21) is unique key. Therefore you don't need id.

> CREATE TABLE `listings` (
> `id` int(8) NOT NULL auto_increment,
> `cat_id` int(6) NOT NULL,
> `url` varchar(150) NOT NULL,
> `title` varchar(100) NOT NULL,
> `description` text NOT NULL,
> PRIMARY KEY (`id`),
> KEY `cat_id` (`cat_id`),
> FULLTEXT KEY `description` (`description`),
> FULLTEXT KEY `title` (`title`)
> ) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=1 ;

Ok, the directories are branch nodes of the tree and listings are the leaves, right?

> Suppose I want to search the listings. The search results are ordered
> by relevency. If it matches the listing.title or the
> listing.description, it is a result.

Query example? In particular, I'm interested to know if you scan the whole listing, or do the index range scan, or use an inverted index. Then I can tell if this seach can be compatible with nested intervals, as you ask in the next paragraph.

> Now suppose I want to restrict the search results to a subcategory. How
> can I do it efficently? That is, without reading much disk space,
> without wasting much memory, and without checking if each result if
> it's in the subcategory.

Nested Intervals searching within a subcategory is index range scan. Depending how you search the listings, it may be compatible with your search. Anyway, I don't see why you have two tables. If you combine them together

CREATE TABLE `directoryListings` (
 `name` varchar(100) NOT NULL,

   `a11` int(8) unsigned NOT NULL,
   `a12` int(8) unsigned NOT NULL,
   `a21` int(8) unsigned NOT NULL,
   `a22` int(8) unsigned NOT NULL,
   `url` varchar(150) NOT NULL,
   `title` varchar(100) NOT NULL,
   `description` text NOT NULL,

   PRIMARY KEY (`id`),
   KEY `cat_id` (`cat_id`),
   FULLTEXT KEY `description` (`description`),    FULLTEXT KEY `title` (`title`)
) ;

then you might introduce composite index. Although 'FULLTEXT' indicates that you are most likely use inverted index. Let me figure out if inverted index can be combined with normal index... Received on Sun Nov 20 2005 - 05:16:55 CET