What storage engine should I use for this MySQL table?
When it comes to InnoDB, you should never use big primary keys. Why?

InnoDB has an internal Clustered Index called gen_clust_index. When you are doing INSERTs into an InnoDB table with just a Primary Key, you are building up the gen_clust_index. I would expect this table to bloat very quickly. Your goal should be to record the URL and index it in such a way that the primary is not large and causing potentially make for slow INSERTs. Given the size of the field, I wouldn't even create a secondary index

This table could easily be a MyISAM table. However, in a high-traffic environment, each INSERT into a MyISAM table would produce a full table lock. That's an automatic bottleneck just to record a URL. So, MyISAM is out. Making the table InnoDB allows a high-traffic environment the freedom to INSERT without locking.

I would like to suggest the following approach:

CREATE TABLE url_trail
(
    id int not null auto_increment,
    url_md5 VARCHAR(32),
    url VARCHAR(255),
    PRIMARY KEY (id),
    KEY url_md5 (url_md5),
    KEY url (url (50))
) ENGINE=InnoDB;


Using this type of layout will allow you to index the MD5 o the URL (32 btyes) rather than the 200+ character URL. There is also an optional index on the first 50 characters of the URL. You could use either index or both.

You will have to do INSERTs like this:

INSERT INTO url_trail (url,url_md5) VALUES ('www.yahoo.com',MD5('www.yahoo.com'));


You will have to do searches like this:

SELECT * FROM url_trail WHERE url_md5 = MD5('www.yahoo.com');
SELECT * FROM url_trail WHERE url = 'www.yahoo.com';


The essential thing overall is to not to have bloated primary keys.