title: SQL - Is the time complexity for foreign keys O(1)?
body: <p>Let's say I have this kind of data for example:</p>
  
  <pre><code>User:
  -id
  -name
  
  Comment:
  -id
  -user id (FK)
  -content
  </code></pre>
  
  <p>So when I'm querying the DB to find the user who is related to a comment, does it go through all the rows in Users until it finds a user with the correct id (O(n))?<br>
  Or is it indexed like some sort of a hash table, and the DB knows immediately where to find the user (O(1))?</p>
  
  <p><strong>UPDATE:</strong>
  OK obviously I need to rephrase: Is it <strong>possible</strong> to make this O(1) with proper indexing?</p>