In the subway, when we bring the card to the terminal, in less than a second either red or green light comes on. That is, the terminal in such a short time should check whether the ID of our card is on the stop-list of the multi-million base. Either I do not understand well (I don’t know at all) how terminals work in the subway, or there is some kind of algorithm that allows you to do all this so quickly. Are there any links where they talk about how the terminal works in the subway (inside) or about what kind of algorithm is used there? Tell me, please, I will be grateful.
- Read something about the basics of databases. In any database, indices are used, which are usually presented as a binary search tree ( ru.wikipedia.org/wiki/… ). The number of operations required to search for such a tree is the binary logarithm of the database size. Let's say for 100 million cards it’s just 28 steps. - Mike
|