Finally a SME question, so my first answer to the forum.
1. Policing has a long history as being an all-community tasks. When populations are small, and movement between communities limited, it would be quite easy for most petty crime to be dealt with, within the community. This maybe mob justice, or formal hearings in front of the all powerful local lord. See Nights Watch for how this was implemented (https://en.wikipedia.org/wiki/Watchman_(law_enforcement))
2. The first civilian policing service you probably are familiar with is Peel's London Metro Police (https://en.wikipedia.org/wiki/Metropolitan_Police_Act_1829). By then London had 2 million people, so it is easy to be unidentifiable whilst you commit crimes, the community run policing doesn't work. Prior to this courts would issue arrest warrants, and private 'thief catchers' would use citizen arrests powers to drag people before the court - often paid for by the victim. (https://en.wikipedia.org/wiki/Thief-taker)
3. A few proto-police forces prior to Peels Police are the Roman Praetorian Guard later supplemented by the Urban Cohort (https://en.wikipedia.org/wiki/Cohortes_urbanae) and French Maréchaussée (https://en.wikipedia.org/wiki/National_Gendarmerie#Early_history_of_the_institution). | Both start life as the king's(or emperors) personnel guard force, and their presence signaled the kings personal interest in matter. Also not all government enforcement isn't all about criminal justice that came about later in history - for example customs inspectors or tax collecting - both pre-modern.
4. 3A. Prior to the praetorian Guard Ancient Roman republic also featured magistrates who could order anything (judge equivalent) they would have Lictors follow, but who could en-act anything the magistrate demanded.(https://en.wikipedia.org/wiki/Lictor)
5. 3B. 164
The French Maréchaussée became French Gendarmes, they were almost all ex-military, moved away from their local province and severed the King not local lords. They would police towns ensuring they providing conscripts to the national army, policed the roads between towns, police vagrants who moved between towns (which locals hated at untrustworthy). Over time they would be the butting heads representing the Kings laws against the Local lords, their laws (and their police).
6. 3C. Ancient Rome sold the right to collect taxes to private contractors. The sale of the contract was the "tax paid" and the government didn't care what happened next. I think for large parts of history this was how it worked. The Lord in charge of salt duties at the port would pay $10,000 to the king, collect $20,000 in taxs - keep the profit.(https://en.wikipedia.org/wiki/Publican)
Something going forward.
1. They key thing is the police would serve the powers that be (either rule of law as set by parliament, independent judiciary, king or lord). This may not align with community expectations. Unlike today's central authority, you could have competing police forces one enforcing the kings laws, the other enforcing community laws.
2. No one cared about petty crime and policing until the population is so large the community can't self police anymore. Until then the police operate to enforce other laws - like conscription that the community would not enforce.
3. Not really raised before but the police only gather evidence to the extend the person deciding guilt needs it. This mean if their is no fair trials, their is no need for evidence gathering.
4. Policing by the state could be substituted for sold rights to enforce ; or citizen rights to enforce. 442