sql >> Databasteknik >  >> RDS >> Mysql

index på url eller hashing med tanke på RAM

Efter att ha läst alla dina frågor ( unik begränsning gör hash värdelös? , 512 bitars hash vs 4 128bit hash och komprimering av webbadresstext (inte förkortning) ) och lagra i mysql ), Jag förstod att ditt problem är mer eller mindre följande:

Är det det?

Följande punkter är viktiga:Hur är formatet på webbadressen som du ska spara? Behöver du läsa tillbaka webbadressen eller bara uppdatera information om den, men aldrig söka baserat på partiella webbadresser, etc?

Förutsatt URL ="http://www.somesite.com.tv/images/picture01 .jpg " och att du vill lagra allt, inklusive filnamnet. Om det är annorlunda, vänligen ange mer information eller korrigera mina svarsantaganden .

  1. If kan spara utrymme genom att ersätta någon grupp av tecken i URL:en. Alla ASCII-tecken är inte giltiga i en URL, som du kan se här:RFC1738 , så att du kan använda dem för att representera (och komprimera) URL:en. Till exempel:om du använder tecknet 0x81 för att representera "http://" kan du spara 6 tecken, 0x82 för att representera ".jpg" kan spara ytterligare 3 byte, etc.

  2. Vissa ord kan vara mycket vanliga (som "bild", "bild", "video", "användare"). Om du väljer att använda tecken 0x90 upp till 0x9f + något annat tecken (alltså 0x90 0x01, 0x90 0x02, 0x90 0xfa) för att koda sådana ord, kan du ha 16 * 256 =4 096 "ordboksposter" för att koda de mest använda orden. Du kommer att använda 2 byte för att representera 4 - 8 tecken.

Redigera: som du kan läsa i nämnda RFC ovan, i URL:en kan du bara ha de utskrivbara ASCII-tecknen. Detta innebär att endast tecken 0x20 till 0x7F ska användas, med vissa observationer gjorda i RFC. Så, alla tecken efter 0x80 (hexadecimal notation, skulle vara tecken 128 decimal i ASCII-tabellen) bör inte användas. Så om kan välja ett tecken (låt oss säga 0x90) som en flagga för att indikera "följande byte är en indikation i ordboken, indexet som jag kommer att använda". Ett tecken (0x90) * 256 tecken (0x00 upp till 0xFF) =256 poster i ordboken. Men du kan också välja att använda tecknen 0x90 till 0x9f (eller 144 till 159 i decimal) för att indikera att de är en flagga till ordboken, vilket ger dig 16 *256 möjligheter...

Dessa två metoder kan spara mycket utrymme i din databas och är reversibla, utan att behöva oroa dig för kollisioner etc. Du skapar enkelt en ordbok i din applikation och kodar/avkodar webbadresser med den, mycket snabbt, vilket gör din databas mycket lättare.

Eftersom du redan har +50 miljoner webbadresser kan du generera statistik baserat på dem för att skapa en bättre ordbok.

Använda hash :Hashes, i det här fallet, är en avvägning mellan storlek och säkerhet. Hur illa blir det om du får en kollision? Och i det här fallet kan du använda födelsedagsparadoxen a> för att hjälpa dig.

Läs artikeln för att förstå problemet:om alla indata (möjliga tecken i webbadressen) var likvärdiga, skulle du kunna stimulera sannolikheten för en kollision. Och skulle kunna beräkna motsatsen:med tanke på din acceptabla kollisionssannolikhet och ditt antal filer, hur brett bör ditt räckvidd vara? Och eftersom ditt intervall är exakt relaterat till antalet bitar som genereras av hashfunktionen...

Redigera: om du har en hashfunktion som ger dig 128 bitar, har du 2^128 möjliga utfall. Så ditt "intervall" i födelsedagsparadoxen är 2^128:det är som att ditt år har 2^128 dagar istället för 365. Så du beräknar sannolikheten för kollision ("två filer vara född samma dag, med ett år som har 2^128 dagar istället för 365 dagar). Om du väljer att använda en hash som ger dig 512 bitar, skulle ditt intervall gå från 0 till 2^512...

Och återigen, ha RFC i åtanke:inte alla byte (256 tecken) är giltiga i internet-/URL-världen. Så sannolikheten för kollisioner minskar. Bättre för dig :).




  1. Få ID:t för en ny post insatt i en databas från den returnerade Uri

  2. Lagrad procedur för att få information om databastabeller

  3. org.postgresql.util.PSQLEUndantag:FATAL:ledsen, för många klienter redan

  4. Använder MySQL relationsdatabaser på Gentoo