title: Database internals: implementation of a foreign key constraint
body: <p>How is the foreign key implemented, for example, in PostgreSQL? </p>
  
  <p>I noticed that a lot of hashing is involved in the creation of a foreign key, so I suppose that a hash based index is created on the foreign key column that references the primary key column. If so (for instance, when we want to remove a row from the referenced table - this one with the primary key or the so called master table) we can easily check if the row from the referenced table is actually referenced or not. What's more, probably DBMS requires that there is at least a B+ tree index on the referenced primary key column, because when we want to insert a new row to the referencing table, we can easily check if a row with the required primary key value exists in the referenced table. Some sources claim that a trigger is used to ensure the foreign key constraint.</p>