3

What I am storing

I'm trying to store a list of URLs and nothing else. My goal is to have a list of blacklisted URLs and I can add to this list when I want and I want to read from the list with O(1) time complexity if possible.

I've read a few answers here where it was suggested that it can be a good design to create a table with only one column if really needed.

How I'm storing

Of course, having only one column means having only the primary key stored. In this case, the MD5 hash of the URL is generated and inserted into the database as the primary key. The list can be very large (hundreds of thousands) but collisions are unlikely so they're not important for now. So just imagine they won't happen. I'm using MySQL if that matters.

My question

  1. What is the time complexity of adding a new URL to this database?
  2. What is the time complexity of checking if a URL exists?

Also, any sample query for table creation, insert, and update is appreciated as I'm new to SQL.

thedatagenes
  • 33
  • 4

2 Answers2

3

The only way to read something with O(1) time in SQL is to use a hash index -- and even that is going to take longer when the hash fills up.

That said, you can learn about hash indexes in the documentation.

That said, I doubt you really need one. A b-tree index is fine for most purposes, and O( log(n) ) is not really noticeable on the data volumes in databases. But, your question specifies O(1) rather than "fast enough", so learn about hashing and hash-based indexes.

Gordon Linoff
  • 1,242,037
  • 58
  • 646
  • 786
2

I suggest creating an index on that table, it being a b-tree index would give time complexity of O(log n) to search. This will scale a lot better for concurrent access. In absence of the index it will be a full table scan for every request and the time complexity of that is O(n), when it is done in parallel it mayn't scale that well. Inserting into this table will be slower if there is an index vs no index. Assuming that insertion doesn't happen as frequently as search, that little bt of extra time won't hurt.

Salim
  • 2,046
  • 12
  • 13