Atualizar lista classificada - banco de dados, algoritmo, classificação, microsserviços, lista de classificação

Eu acho que existe um nome comum para o algoritmo que estou pesquisando.

Eu tenho uma grande lista de jogadores classificados por seusPonto. por exemplo, 1 milhão ou bilhão de jogadores. A cada segundo que um jogador está alterando sua pontuação, desejo atualizar a lista classificada para mantê-la classificada e desejo conhecer uma nova posição do jogador.

Posso atualizar a pontuação e reordenar a lista de furos. (não eficiente) ou posso re-classificar de [oldpos, newpos] (melhor) ou posso mover o jogador e mudar outros jogadores. (melhor)

Existe nome para esse algoritmo?

Está correto que os bancos de dados regulares não manejem essa tarefa com eficiência e eu tenho que desenvolver serviços em Java, C #, Go, etc., que manterão a lista classificada na RAM e farão turnos?

Respostas:

Você pode segurar um Árvore AVL, a operação de inserção e exclusões levou tempo O (logn) nessa estrutura de dados. sempre que precisar atualizar um jogador: remova da árvore, mude a pontuação, insira na árvore.

Essa é a troca exata que você está procurando,todas as operações recebem O (logn) e, como você precisa de todas as operações (pesquisa e atualização - deleteinsert), essa é a melhor correspondência para você. O consumo de memória é O (n) btw.