Proper way to store lots of links?

Question

I'm doing a small crawl over multiple sites and I have a lot of links which are represented by ID's (example.com/foo = 354).

I'm currently storing the link -> link references and the link text. So in the following table page "2845" contains a link to 4479 with the text "About Us". Nothing big, just 3NF.

+----------+----------+-----------------+
| url_1_id | url_2_id | text            |
+----------+----------+-----------------+
|     2845 |     4479 | About Us        |
|     2845 |     4480 | Who We Are      |
|     2845 |     4481 | What We Do      |
|     2845 |     4482 | Core Principles |
|     2845 |     4483 | Research Staff  |
+----------+----------+-----------------+

However, by my calculations (most of the pages containing 500-1000 links each) I should have 6GB of link data by the time I've only parsed 200k pages.

Is there a better way to store link data? Especially if there is a good way to normalize repeated navigation menus for all site pages.

Answer 1

If you can't or won't use a Graph DB (which should be the optimal DB for this type of application), then you can test a slightly more abstract breakdown of the data. Here is one approach I would take towards your task.

First, you have specific URL Links. That would be, for example, the link to joanolo, https://dba.stackexchange.com/users/112361/joanolo, found at the end of the other answer. There may be more than one such link on a page (i.e. joanolo's comments each have the same link). How do you want to handle multiple identical links on a page? I have chosen to handle identical links a specific way, discussed below. I define the table to handle the URL Links like this:

CREATE TABLE URLLinks (
    URLLinksID bigint identity(1,1),
    URLParams nvarchar(max) NULL,
    URLsID bigint not null,
    secure bit default 0 not null,
    CONSTRAINT pk_URLLINKS Primary Key (URLsID, URLParams, Secure) 
    )

Note that an URL Link includes any parameters on the link, and whether or not the connection is secure or not. For this first pass, I am ignoring alternate types of links, such as ftp://

The URLsID field in the URLLinks table is a reference to the URLs table. This contains the text of the URL, e.g. dba.stackexchange.com/users/112361/joanolo in the sample URL above. Any link that has this as the URL will reference this URLs entry by URLsID. Here is the very simple URLs table:

CREATE TABLE URLs (
    URLsID bigint identity(1,1),
    URLText nvarchar(max) not null
    )

Between these two tables, we have all of the information we need to recreate the URL, including any parameters, without duplicating the URLText.

Note that if it was worthwhile, we could break the URLText into a chain of smaller pieces, and build a URL chain linking the correct pieces together. I wager that this linking, with an 8-byte ID pointing to each piece, the parent piece (if any), and the Chain (24 bytes + overhead) is going to be more costly in space and overhead than working with the URLs text directly, so I am not exploring that path now.

To associate a link with its page, there is the URLRefs table:

URLRefs (
    URLID bigint not null,
    ParentURLID bigint not null,
    LinkText nvarchar(max) not null,
    LinkCount int default 1 not null
    )

Notice the field LinkCount. This will count the number of times the same URLLink occurs on the page, rather than having a separate entry for each occurrence. This may or may not save space and effort overall, but it does hear on dba.stackexchange.com, so I went with this method. On sites where links are never duplicated on a page, this will always be 1.

With these elements, you should have the most compact non-graph depiction of pages with URLs pointing to pages with URLs pointing to... (Unless you build special cases to handle e.g. menus, as joanolo suggested.)

As an example, the joanolo link as shown above will have just one entry in URLLinks, one entry in URLs, and one entry in URLRefs for each different page the link appears on. If he has 500 such links across 100 pages, he will still have only one link in URLs and URLLinks, and 100 entries in URLRefs.

Answer 2

Possible approaches:

1. If your problem is well represented by a graph (and I think it is), I'd suggest that you consider using a Graph Database. It's optimised for this kind of scenarios: you have pages (nodes), you have links between pages (verticies), and you have some attributes associated to either one of them. Check Neo4J or OrientDB to get a feeling for what they could do in your scenario.

---

2. If you want to save some space, consider a way to represent menus in a compact way. That is, there will be a very large number of cases like:

   page1 - links_to - home
   page1 - links_to - legalese
   page1 - links_to - the_company
   page1 - links_to - our_products
   page1 - links_to - our_services
   page1 - links_to - contacts

   page1 - links_to - something unique or not common 1
   page1 - links_to - something unique or not common 2

   and then again

   (same for page2)
   (same for page3)

   if you identify this structure, you can create some "meta-structure" such as "standard_menu". (The difficult part of this approach is deciding what collection of links should be considered a menu and which are not, and small differences such as a page containing a menu with a slight variations [such as "I don't link to myself"]).

This data structure should help you:

CREATE TABLE urls
(
    id_url serial PRIMARY KEY,
    url text NOT NULL,
    UNIQUE(url)
) ;

CREATE TABLE menus
(
    id_menu serial PRIMARY KEY
) ;

CREATE TABLE menu_links
(
    id_menu integer not null REFERENCES menus(id_menu),
    id_url_to integer not null REFERENCES urls(id_url),
    link_text text not null,
    PRIMARY KEY (id_menu, id_url_to)
) ;

CREATE TABLE from_page_to_page
(
    id_url_from integer not null REFERENCES urls(id_url),
    id_url_to integer not null REFERENCES urls(id_url),
    link_text text not null,
    PRIMARY KEY (id_url_from, id_url_to, link_text)
) ;

CREATE TABLE from_page_to_menu
(
    id_url_from integer not null REFERENCES urls(id_url),
    id_menu integer not null REFERENCES menus(id_menu),
    PRIMARY KEY (id_url_from, id_menu)
) ;

And finally, you can have a view that puts together the equivalent of your existing table by making a UNION of the "menu links" and the "non-menu links":

CREATE VIEW all_links AS

SELECT 
    id_url_from, id_url_to, link_text 
FROM 
    from_page_to_page
UNION ALL
SELECT 
    id_url_from, id_url_to, link_text
FROM 
    from_page_to_menu
    JOIN menu_links ON menu_links.id_menu = from_page_to_menu.id_menu ;

Alternatively, you could always change the name "menu" by "link_group", every time you have something like:

page1 - links_to - page_a
page1 - links_to - page_b
page1 - links_to - page_c
page1 - links_to - page_z

page2 - links_to - page_a
page2 - links_to - page_b
page2 - links_to - page_c
page2 - links_to - page_y

page3 - links_to - page_a
page3 - links_to - page_b
page3 - links_to - page_c
page3 - links_to - page_x

(ignoring text labels, these are actually 12 pairs of numbers)

you could convert it into:

link_grup_1 - page_a
link_grup_1 - page_b
link_grup_1 - page_c

page_1 - link_grup - link_grup_1
page_1 - links_to - page_z
page_2 - link_grup - link_grup_1
page_2 - links_to - page_y
page_3 - link_grup - link_grup_1
page_3 - links_to - page_x

(these are only 9 pairs of numbers).

The savings will grow as soon as the number of items common to many pages is more than just two or three.