The database uses indexes . Thus, he can quickly find data related to a specific user ID.
Depending on the structure of the index, occupation of space, etc. is the gain, i.e. instead of looking for N columns, it searches - for example - log(N) . 100 billion line search dichotomy
N = 100,000,000,000
will be
Search(N) : search log2(N) = search (36 rows)
Instead of searching for 10 ^ 12 lines, only 36 lines need to be analyzed.
In the case when you mention friends, each user can have several friends, therefore
user1 => (userX, userY, userZ, ...) userX => (userU, userV, user1, ...)
means user1 is friend with userX, userY etc .... i.e. You do not have a unique index for each user. But you have a unique index for a couple of users.
on mysql which would be
UNIQUE(user1,user2)
means that the pair (user1, user2) is found only once in the table. The syntax will be
CREATE UNIQUE INDEX friendsindex ON friends(user1,user2)
friendsindex - index name, friends - table. Or, as you said, declaring the primary key of the table (user1,user2) (primary keys are unique to each table).
-
The strategy to win a game consisting in finding the exact price of a given object is based on the same principle. Let's say the price is between 1 and 10,000. You say the price, and the handler says + or - . You should find the price as few attempts as possible. For instance. the price is 6000.
You can start at 1 and give all prices up to 6000 (i.e. 6000 attempts), but you can also continue the dichotomy
- you: 5000
- gamer: +
- 7500 or (10000 - 5000) / 2
- -
- 6250 or (7500 - 5000) / 2
- -
- etc...
you divide the remaining range by 2 at each iteration. Instead of 6000 attempts, you can find in 12 attempts (log2 (6000)).
-
About logarithms
For example, how to find x in 2^x = 1024 ? Or x = log2(1024) means the logarithm of 1024 in base 2 (answer: 10). In our history, a 1024-row table with a binary tree-based index needs 10 attempts (max) to find the correct item (instead of 1024 max).