Many documents explain how Kubernetes objects (pods, services...) can be labeled and how to filter/query objects using them.

But none explains how they manage the metadata/labels! (I tried to find anything but no luck... :( )

I wonder what happens under the hood if I enter

1) kubectl get deploy my-deploy-name
2) kubectl get deploy -l app=my-app-label

I already know the actual api call for this command would be

GET /apis/apps/v1/namespaces/{namespace}/deployments/{name}?labelSelector={key}%3{val}

But I mean, how they search specific object ? I guess there should be any data store to manage metadata/labels. If not, Kubernetes somehow has to scan all the object resources and this doesn't sound efficient.

And what time complexity would be if I search any object using metadata name/labels ?

Please help me and thank you in advance ;)