DEV Community

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

Collapse
 
mohamed profile image
Mohamed Saad

Hey rhymes

I don't think the problem mentioned here is choosing between ORM and raw SQL.

The main problem is how to store data and how to retrieve them.

First, you mentioned the first 50 item ahead of the whole data then reload it with another 50 and so on. This is okay of course. However the 50 data is previously organized in a way that let those 50 comes first from all those main data.

I have a lot of cases in my mind . I will try to add them as I remember to discuss

1 - If someone signs up in your website : it will add his email after the last signed up person.... 1,2,3,4,5,6,7,8,9 ,.............., 5,000,000

How can I authenticate the id=4,000,000 for example ( mr.example@gmail.com)
as I understand it will loop through all emails till it finds ( mr.example@gmail.com) then compare the hashed value of the given password with the stored one in the database. Correct me if I am wrong.

2- Imagine searching "Data structures" term in udemy. It will get all general data structures courses then data structures using specific language like java or c++ or python. this query will also maintain the first courses to be the highest rated.

3- friends of friends in facebook

I do think there are a lot of cases and as I mentioned I will add some later on.

I'm open for discussions anytime

Collapse
 
rhymes profile image
rhymes • Edited

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: postgresql.org/docs/10/static/inde...

  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: quora.com/How-does-Facebook-mainta...

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