Each CPU's runnable tasks sit in a red-black tree keyed by virtual runtime, the CPU time a task has already had, scaled by its priority. CFS ran the smallest key next, which is the leftmost node, and the kernel caches a pointer to it so the pick costs nothing. When a task is descheduled its vruntime has changed, so it is removed and reinserted at its new position, which is why the ordering has to be cheap to maintain and not merely cheap to read. Linux 6.6 replaced CFS with EEVDF, which keeps the same tree but picks by virtual deadline instead of always taking the leftmost node.