Fizikai tervek 2 - Rendezett állomány
- Egy mező (rendező mező) alapján rendezett blokkok láncca
- Tehát a következő blokkban már nagyobbak az elemek (duh)
- Ha a rendező ls kereső mező nem esik egybe, akkor kopac rendezés kell
- Ha a kereső és rendező mező egyezik, akkor a bináris keresés működik
- Beolvassuk a középső blokkot
- Ha nics benne az
A=a rekord, akkor a rendezettség miatt tudod merre kell menni...
- Ismételd amíg meg nincs, vagy a lánc már csak 1 blokk hosszú
Rendezett állomány - Beszúrás
- Keresés
B/2 , beszúrás után (lehetséges) átrendezés
B/2 , tehát B
Beszúráshoz Keresés
- Gyűjtő (túlcsordulási) blokk itt is van
- Keresés két helyen:
- \(\log_2\)(
B - G) költséggel a rendezett részen
G költséggel a (nem rendezett) gyűjtőn- Összköltség \(\log_2\)(
B - G) + G
- Ha a
G túl nagy a \(\log_2\)(B)-hez képest, akkor történik újrarendezés
- Rendezés össz költsége
B\(~\times~\log_2\)(B)
Üres helyek keletkezhetnek:
- Félig üres blokkok
- Keresés után 1 művelet visszaírni új rekordot
- Tárméret
2*B
- Keresési idő \(\log_2(\)
2*B\()~=~1+\log_2\)(B)
- Ha egy blokk betelik, vagy a telítettség elér egy kikötött küszöböt, akkor két blokkra bontjuk szét a rendezhetőség miatt
Rendezett állomány - Törlés
- Keresés + a törlés művelete (esetleg csak törlési bit utáni visszaírás)
- Túl sok törlés után újraszervezés
Rendezett állomány - Módosítás