DEV Community

Discussion on: How can We implement Data Structures and Algorithms in Backend Frameworks to reach O(log(n)) Run Time ?

rhymes profile image
rhymes • Edited on

There are a few different things:

  1. to solve the problem of "find the nth million user and check its password", assuming you have it's email or id or whatever you can use indexes. Most databases have it. Instead of traversing millions of rows you just find the right one through the index. PostgreSQL has different types of indexes:

  2. that's probably implemented using a full text search with weights: Full Text Search Explained

  3. that's one of the hardest things to implement at scale. That's why Facebook is as big as Facebook ;-) Jokes aside, I would look into graph theory. You could probably implement a super simple version with a traditional database but it would probably explode if you have billions of users like FB. You might get by using Redis but you'll still have scaling problems. There's a discussion on the topic here:

1 and 2 are "free" in basically all relation database systems. 3 requires non trivial logic and implementation.