Listepartisjonering

Listepartisjonering er prosessen med å dele en liste av elementer inn i to eller flere disjunkte partier som til sammen inneholder alle elementene. Hver partisjon består av elementer som oppfyller en felles betingelse, som en predicate, en nøkkelverdi eller et intervall av verdier. Partisjonering brukes for å organisere data slik at visse operasjoner kan utføres mer effektivt, spesielt i sammenhenger med søk, filtrering, parallell behandling eller distribusjon av arbeid.

Partisjoner kan baseres på ulike kriterier. Predikatbasert partisjonering deler elementene etter en logisk betingelse (for eksempel alle elementer med attributt X: ja). Nøkkelbasert eller hash-basert partisjonering bruker verdien av et eller flere felter for å tilordne elementer til spesifikke partier. Rangebassert (range) partisjonering deler elementer inn i intervaller av verdier. Partier kan være to eller flere, og i noen tilfeller kan de være like store eller balanserte for å jevne arbeidsbelastningen.

Metoder for å oppnå listepartisjonering inkluderer enkel gjennomgang og sortering, samt in-place-partisjonering som ofte brukes i sorteringsalgoritmer. I større data- og databasesammenhenger brukes bucketing eller hash-baserte løsninger for å distribuere arbeid mellom prosesser eller maskiner.

Bruksområder omfatter databasedharging og fragmentering, parallell behandling i datafløyer og forberedelse av data til analyse eller maskinlæring. Fordeler inkluderer bedre cachelokalitet, mulighet for parallellisering og potensielt bedre skalerbarhet. Utfordringer inkluderer risiko for skjevfordeling mellom partier og ekstra overhead ved oppdatering eller vedlikehold av partisjonene.

Se også: partisjonering, bucketing, sharding, klynger, datadistribusjon.