บทที่ 5 Organizing Files for Performance
หัวช้อที่กล่าวถึงมีดังนี้
- Data Compression
เป็นเทคนิคการทำให้แฟ้มข้อมูลขนาดใหญ่ เป็นแฟ้มขนาดเล็ก (บีบอัด)
- Reclaming Space in Files
นำ Record ที่ Delete กลับมาใช้ประโยชน์ได้อย่างไร
- An Introduction to Internal Sorting and Binary Search
การเรียงลำดับข้อมูล
- Key sorting
เป็นเทคนิคการ Sort ใน Ram
5.1 Data Compression
เป็นเทคนิคที่เราจะ Encode แฟ้มข้อมูลขนาดใหญ่ ให้มีขนาดเล็กลง ซึ่งมีหลายเทคนิค
เหตุผลที่ต้องทำ Data Compression
- ใช้เนื้อที่ในการเก็บข้อมูลน้อยลง ค่าใช้จ่ายที่ต้องเสียไปในการบันทึกข้อมูลก็จะน้อยลง
- ทำให้การโอนถ่ายข้อมูลในระบบเครือข่ายได้เร็วขึ้น
- ทำให้การประมวลผลกับแฟ้มข้อมูลได้เร็วขึ้นเพราะใช้เวลาในการ Access time น้อยลง
วิธีการทำ Data Compression
- Using Different Notation
- เป็นการใช้เทคนิค redundancy reduction คือการลดขนาดแฟ้มข้อมูลให้มีขนาดเล็กลง โดยที่ข้อมูลไม่สูญหายไปไหน เช่น การใช้อักษรย่อแทนชื่อเมือง ตัวอย่างการเก็บชื่อรัฐของ U.S.A มี 52 รัฐ อาจใช้เนื้อที่เพียง 6 bit เพื่อประหยัดเนื้อที่
ข้อเสีย
?
ข้อมูลที่เก็บไม่สื่อความหมายกับมนุษย์ ต้องเขียนโปรแกรมแปลง เช่น 010101 แทน OK เป็นต้น
?
ค่าใช้จ่ายที่ต้องเสียให้กับการใช้เทคนิคนี้
Suppressing Repeating Sequences
- เป็นการใช้เทคนิค run-length encoding คือการลดขนาดแฟ้มข้อมูลให้มีขนาดเล็กลง โดยการนับจำนวนที่ซ้ำและแทนด้วยจำนวนตัวเลขที่นับได้ และตามด้วยรหัสของข้อมูลตัวนั้นที่มีการซ้ำกัน
- ข้อมูลที่มีค่าซ้ำๆ กัน ก็จะเก็บเป็น Code แทน และบอกถึงจำนวนของข้อมูลที่ซ้ำกันว่ามีกี่จำนวน
ตัวอย่างแบบฝึกหัดท้ายบทหน้า 219
„
A. 01 01 01 01 01 01 01 01 01 01 02 03 03 03 03 03 03 03 04 05 06 06 07
สามารถแทนด้วยการ run-length encoding ได้ดังนี้
FF 01 09 02 FF 03 07 04 05 FF 06 02 07
B. 01 01 02 02 03 03 04 05 06 06 05 05 04 04
FF 01 02 FF 02 02 FF 03 02 04 05 FF 06 02 FF 05 02 FF 04 02
(Code FF แทนในกรณีที่ข้อมูลช่วงนั้นๆ ซ้ำติดต่อกันมากกว่า 1 และบอกข้อมูลอะไรที่ซ้ำ, บอกจำนวนที่ซ้ำ
- Assigning Variable-Length Codes
- ใช้เทคนิค Huffman Code
- มีการสร้างเป็น Binary tree เพื่อแทนชุดข้อมูล โดยมีการกำหนดให้ค่าของข้อมูลที่เกิดขึ้นบ่อยมีเส้นสั้น
ตัวอย่าง
|
Letter |
a |
b |
c |
d |
e |
f |
g |
|
Probability |
0.4 |
0.1 |
0.1 |
0.1 |
0.1 |
0.1 |
0.1 |
|
Code |
1 |
010 |
011 |
0000 |
0001 |
0010 |
0011 |
หาค่าความน่าจะเป็นแล้วเรียงจากมากไปน้อย จากนั้นจับตัวล่างบวกกัน
|
Letter |
Prob. |
Code |
1 |
2 |
3 |
4 |
5 |
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
0.4 |
1 |
0.4 |
1 |
0.4 |
1 |
0.4 |
1 |
0.4 |
1 |
0.6 |
0 |
|
b |
0.1 |
010 |
0.2 |
001 |
0.2 |
000 |
0.2 |
01 |
0.4 |
00 |
0.4 |
1 |
|
c |
0.1 |
011 |
0.1 |
010 |
0.2 |
001 |
0.2 |
000 |
0.2 |
01 |
|
|
|
d |
0.1 |
0000 |
0.1 |
011 |
0.1 |
010 |
0.2 |
001 |
|
|
|
|
|
e |
0.1 |
0001 |
0.1 |
0000 |
0.1 |
011 |
|
|
|
|
|
|
|
f |
0.1 |
0010 |
0.1 |
0001 |
|
|
|
|
|
|
|
|
|
g |
0.1 |
0011 |
|
|
|
|
|
|
|
|
|
|
ข้อมูลเดิมคือ
abde หลังจาก encode แล้ว 101000000001
หรือ dacab หลังจาก encode แล้ว 000010111010
Irreversible Compression Technique
สละข้อมูลบางส่วนเพื่อให้แฟ้มข้อมูลมีขนาดเล็กลง ทำให้สูญเสียข้อมูลบางส่วน
ไม่นิยมที่จะ compression แฟ้มข้อมูลประเภท data, text จะเหมาะกับ ไฟล์เสียง (การอัดเทป จะตัดส่วนที่เว้นช่วงจังหวะไม่มีเสียงพูด), ไฟล์รูปภาพ (มีจุดขาว-ดำ)
- Compression in OS
- ระบบ Unix จะมี utility File ที่ใช้ในการ Compression เช่น jzip, gunzip, compress, uncompress, File ข้อมูลจะมี extension เป็น File.gz, File.tar งานประเภทรวมหลายๆ ไฟล์ไว้ในไฟล์เดียว
5.2 Reclaming Space in Files
- นำพื้นที่ที่เป็นส่วนที่ Delete record กลับมาใช้ (พื้นที่ในส่วนนั้น)
การทำงานกับไฟล์มีดังนี้
- Record addition; à
เพิ่มข้อมูลที่ท้ายไฟล์ แล้วใช้ pointer ชี้ไปที่ตำแหน่งที่ Append เข้ามา
- Record update; and à
การทำงานที่จะกระทำกับ record เช่น Delete ของเก่า แล้วเพิ่มของใหม่เข้าไป
- Record deletion à
ไม่สนใจ record เก่า ถ้ามี record ใหม่ จะนำไปต่อท้ายไฟล์
5.2.1 Record Deletion and Storage Compaction
กรณีที่มีการลบ Record อาจให้มี * mark บอก status การลบ เมื่อต้องการเอาเนื้อที่ที่เก็บ record เหล่านี้มาใช้อาจให้มีการเรียกใช้ program เพื่อให้ clear เนื้อที่ในส่วนนั้นกลับมาใช้งานอีก
5.2.2 Delete Fixed-Length Records for Reclaiming Space Dynamically
- อาศัยการ mark ว่า record ถูก delete
- หาวิธีการที่จะหา record ที่ถูก delete ไป เพื่อนำเนื้อที่ส่วนนั้นกลับมาใช้ประโยชน์ต่อไป แล้วเอา record ใหม่ไปใส่แทนที่
การ Implement
- ใช้ link-list มาช่วยเก็บ record ที่ถูก delete ไป เรียกว่า avail list
- ใช้ stack ในลักษณะที่นำ record ที่ถูก delete ไปเก็บลง stack เมื่อมี record ใหม่ จะตรวจ stack ถ้าเจอ record ที่ถูก delete จะ pop ออกมา และเอา record ใหม่ ไปแทนที่
5.2.3 Delete Variable-Length Records
- การจัดการกับ record ที่มีความยาวไม่เท่ากัน
- มีการเก็บความยาวของ record ไว้ข้างหน้า
- กรณีที่ค้นหาแล้วไม่เจอพื้นที่ที่จะเอา record ใหม่ไปใส่ได้ จะเอาไปต่อไว้ที่ท้ายไฟล์
ข้อแตกต่างระหว่าง Internal และ External fragmentation
คือเนื้อที่ว่างที่ไม่มีประโยชน์ที่อยู่ภายใน record และเป็น record ประเภท Fixed-length record ซึ่งเนื้อที่ของ record ใหม่ เมื่อทำการแทนที่แล้วจะน้อยกว่า record เดิม เช่น เหลือ 8 byte เอาไว้ทำอะไรไม่ได้
External Fragmentation คือเนื้อที่ว่างที่ไม่มีประโยชน์ระหว่าง record เกิดขึ้นตอนใช้ Variable-Length Record มีช่องว่างเหลือและไม่สามารถนำมาใช้ประโยชน์ได้ โดยเมื่อเนื้อที่ของ record เดิมที่ทำการลบไปแล้ว และมี record ใหม่ซึ่งอาจมีเนื้อที่ (จำนวน byte) มากกว่า ไม่สามารถเก็บ record ใหม่ลงในเนื้อที่บริเวณนั้นได้ ทำให้เกิด external fragmentation หรือถ้ามีการ Add record ใหม่ เข้าไปซึ่งมีเนื้อที่น้อยกว่า อาจจะมีเนื้อที่ว่างเหลืออีกนิดเดียว ซึ่งเอาไว้ทำอะไรไม่ได้ ก็จะเรียกว่า external fragmentation
5.2.4 Storage Fragmentation
เป็นกลยุทธ์ที่ใช้ในการแก้ปัญหา External
- รวมเนื้อที่ว่างที่อยู่ใกล้กัน รวมกันให้มีขนาดใหญ่ขึ้น
- เอา Record ใหม่ไปไว้ที่ไหนดี? ที่ทำให้เกิด fragment น้อยที่สุด
5.2.5 Placement Strategies
เทคนิคที่ใช้จัดการกับ Record ใหม่ ที่จะเอาไปเก็บที่ Storage
เลือกว่าจะนำ Record ใหม่ไปวาง ณ ตำแหน่งไหนของที่ว่าง เพื่อให้เกิด fragment น้อยที่สุด มีวิธีการดังนี้
- First fit หาตำแหน่งว่างตำแหน่งแรกแล้วเก็บ Record ใหม่ ซึ่งจะมีการตรวจสอบขนาด fragment ว่าใหญ่พอหรือไม่ ไม่สนใจขนาดที่ใหญ่กว่า ถ้าพบที่แรกที่สามารถใส่ได้จะนำ record ใหม่ไปใส่เลย
- Best fit หาตำแหน่งที่พอดีกับ Record ใหม่มากที่สุด จะมีการเลือกหรือเข้าไปค้นใน avail ว่ามีตำแหน่งไหนบ้างที่เหมาะสม และเนื้อที่พอดีที่สุดที่จะนำ record ใหม่ไปวาง เพื่อให้เหลือ fragment น้อยที่สุด
- Worst fit หาตำแหน่งที่ว่างที่ใหญ่ที่สุดที่จะใส่ record ใหม่ได้ เพื่อจะได้เหลือ fragment มากเพื่อให้ใส่ record ต่อๆ ไป ซึ่งช่วยลด external fragmentation
ตัวอย่าง
ถ้าเอาข้อมูลที่มี Size = 55 มาใส่
Size
- First fit = 72
- Best fit = 68
- Worst fit = 72
กรณีของ Best fit จะทำให้เกิดการ sort ข้อมูลจากน้อยไปมาก
กรณีของ Worst fit จะทำให้เกิดการ sort ข้อมูลจากมากไปน้อยไป
กรณีของ First fit
An Introduction to Internal Sorting and Binary Search
วิธีการที่จะเข้าถึง Record หนึ่งๆ ได้อย่างรวดเร็ว
ใช้การค้นแบบ Binary Searching โดยการเปรียบเทียบ Record
Binary Search ใช้หลักการ
- ข้อมูลต้องมีการ Sort จากน้อยไปมาก
- หาตำแหน่งค่ากลางเปรียบเทียบ
ต้องการหาค่า 15
2 6 7 10 12 15 17 25 26
á
á
á
ครั้งที่
low=1 mid=5 high=9
‚
low mid
ƒ
high
หา
mid = (low + high)/2
ƒ
หาจนเจอ low=high=mid จึงจะได้ค่า key
- ใช้หลักการแบ่งครึ่งข้อมูล แล้วเปรียบเทียบไปเรื่อยๆ
Binary Search Versus
- มีการเปรียบเทียบโดยเฉลี่ยจะอยู่ใน Order ที่ O (log N)
สัญลักษณ์ ë
xû
= floor แทนเลขจำนวนเติมที่มีค่ามากกว่าหรือเท่ากับ real number
สัญลักษณ์ é
xù
= ceiling แทนเลขจำนวนเติมที่มีค่าน้อยกว่าหรือเท่ากับ real number
5.4 Key Sorting
- เป็นเทคนิคการ Sort ใน Ram
- ยึดหลักการนำข้อมูลมา Sort ใน Ram ซึ่งแฟ้มข้อมูลต้องมีขนาด
ขนาดพื้นที่ใน Ram ที่จะเก็บได้
จะ Sort Record จากค่าของ Key
กำหนด Keynodes 2 ค่า คือ
Keynodes
à
Key
à
RRN (Relative Record Number)
- การค้นหาข้อมูลด้วยวิธีนี้จะมีการ Write ลง File ใหม่ และเรียงลำดับตาม Keynodes RRN
- การทำลักษณะนี้จะค่อนข้างซ้ำซ้อน โดยนำส่วน data เฉพาะชื่อ load ขึ้น memory แล้ว sequential ดังนั้นจึงเกิด Index
ที่จะเป็น Keynodes array
Indexing to Provide Access by Multiple keys
- เป็นการใช้ Key หลาย Key เป็น index
- secondary index สามารถซ้ำกันได้
- primary key จะซ้ำไม่ได้ เป็น key ที่ใช้ identify record หนึ่งๆ
- ตัวอย่าง
Improving the secondary index structure inverted list
การจัดโครงสร้างของ secondary index เพื่อให้เปลืองเนื้อที่น้อยที่สุด
และกรณีที่มี recode ใหม่จะต้องเข้าไป Add ที่ secondary index ซึ่ง