Yioop - PHP Search Engine

Oct 14 In-Class Exercise Thread.

Please post your solutions to the Oct 14 In-Class Exercise to this thread.

Best,

Chris

Please post your solutions to the Oct 14 In-Class Exercise to this thread. Best, Chris

-- Oct 14 In-Class Exercise Thread

1. It'll take 200000 blocks and 819200000 bytes to store R.

2. Number of records that can be stored in a block = 4096/28 = 146.28 ~ 146

3. Number of blocks to store records = 1000000/146 = 6849.31 ~ 6850

Number of bytes to store the above records into block = 6850*4096 = 28057600

4. Block accesses

Without indexes: log-base2(200000) = 17.60 -> 18 accesses
With indexes: log-base2(6850) = 12.74 -> 13 accesses

(Edited: 2020-10-14)

1. It'll take 200000 blocks and 819200000 bytes to store R. 2. Number of records that can be stored in a block = 4096/28 = 146.28 ~ 146 3. Number of blocks to store records = 1000000/146 = 6849.31 ~ 6850 Number of bytes to store the above records into block = 6850*4096 = 28057600 4. Block accesses * Without indexes: log-base2(200000) = 17.60 -> 18 accesses * With indexes: log-base2(6850) = 12.74 -> 13 accesses

-- Oct 14 In-Class Exercise Thread

Number of blocks = 1000000/5 = 200000
Number of bytes = 200k*4096 = 819200 kilo bytes
Number of index records possible in a block = 4096/28 = 146
Number of blocks to store records = 1000000/(146) = 6850 = 28057600 bytes
Number of block accesses with index = log(base2)(6850) = 13
Number of block accesses without index = log(base2)(200000) = 18

(Edited: 2020-10-14)

* Number of blocks = 1000000/5 = 200000 * Number of bytes = 200k*4096 = 819200 kilo bytes * Number of index records possible in a block = 4096/28 = 146 * Number of blocks to store records = 1000000/(146) = 6850 = 28057600 bytes * Number of block accesses with index = log(base2)(6850) = 13 * Number of block accesses without index = log(base2)(200000) = 18

-- Oct 14 In-Class Exercise Thread

 1. (1,000,000 tuples / 5 tuples/block) * 1 block * 4096 bytes  = 819200000 bytes or 819.2 
 MB. R takes 819200000 bytes to store or 200,000 blocks
 2. 4096 bytes / 28 bytes/block = 146.28 or 146 bytes/block
 3. 1,000,000 tuples / 146 bytes/block = 6849.3 or 6849 blocks which is 28,053,504 bytes
 4. Without indexes log_2(200,000 blocks) = 17.6 or 18 accesses. With indexes log_2(6849) = 
 12.5 or 13 accesses.

(Edited: 2020-10-14)

1. (1,000,000 tuples / 5 tuples/block) * 1 block * 4096 bytes = 819200000 bytes or 819.2 MB. R takes 819200000 bytes to store or 200,000 blocks 2. 4096 bytes / 28 bytes/block = 146.28 or 146 bytes/block 3. 1,000,000 tuples / 146 bytes/block = 6849.3 or 6849 blocks which is 28,053,504 bytes 4. Without indexes log_2(200,000 blocks) = 17.6 or 18 accesses. With indexes log_2(6849) = 12.5 or 13 accesses.

-- Oct 14 In-Class Exercise Thread

 1) a.No of blocks = 200,000
    b. No of Bytes = 819,200,000 bytes
 2) Number of index records in block = 146
 3) a.Number of blocks = 1,000,000 /146 = 6850
    b.Number of bytes = 28,000,000

(Edited: 2020-10-14)

1) a.No of blocks = 200,000 b. No of Bytes = 819,200,000 bytes 2) Number of index records in block = 146 3) a.Number of blocks = 1,000,000 /146 = 6850 b.Number of bytes = 28,000,000

-- Oct 14 In-Class Exercise Thread

 1. 200000 blocks; 819,200,000 bytes
 2. 146 index records in block
 3. index file would take 28,000,000 bytes & 6850 blocks
 4. without the index log base 2 (200,000) = 18 accesses  
 5. with index log base 2 (6850) = 13 accesses

(Edited: 2020-10-14)

1. 200000 blocks; 819,200,000 bytes 2. 146 index records in block 3. index file would take 28,000,000 bytes & 6850 blocks 4. without the index log base 2 (200,000) = 18 accesses 5. with index log base 2 (6850) = 13 accesses

-- Oct 14 In-Class Exercise Thread

	1) 1,000,000 tuples / 5 tuples / block = 200,000 blocks. 
	That means we need 4096 bytes/block * 200,000 blocks = 819200000 bytes to store R into to 200,000 blocks

	2) 4096 bytes/block / (20 bytes + 8 bytes)/block/index_record = (4096/28) index_records = 146.285... which goes to 146 index records.

	3) One entry per index record means 1,000,000 entries.  146 records fit into one block, so:
	1,000,000 entries / 146 entries per block = 6849.31 blocks --> 6850 blocks = 28057600 bytes

	4) without the index, we would need log-base 2 (200,000) = 17.609640474 ==> 18 accesses
	with the index, we would need log-base 2 (6850) = 12.741888273 ==> 13 accesses

(Edited: 2020-10-14)

1) 1,000,000 tuples / 5 tuples / block = 200,000 blocks. That means we need 4096 bytes/block * 200,000 blocks = 819200000 bytes to store R into to 200,000 blocks 2) 4096 bytes/block / (20 bytes + 8 bytes)/block/index_record = (4096/28) index_records = 146.285... which goes to 146 index records. 3) One entry per index record means 1,000,000 entries. 146 records fit into one block, so: 1,000,000 entries / 146 entries per block = 6849.31 blocks --> 6850 blocks = 28057600 bytes 4) without the index, we would need log-base 2 (200,000) = 17.609640474 ==> 18 accesses with the index, we would need log-base 2 (6850) = 12.741888273 ==> 13 accesses

-- Oct 14 In-Class Exercise Thread

 Blocks = 200000
 Bytes = 819200000
 Index Records per block = 146
 Index File
	Bytes = 28000000
	Block = 1000000/146 = 6849.31 = 6850
 Block Accesses
	With Index = log(6850) = 12.742 = 13
	Without Index = log(200000) = 17.609 = 18

(Edited: 2020-10-14)

Blocks = 200000 Bytes = 819200000 Index Records per block = 146 Index File Bytes = 28000000 Block = 1000000/146 = 6849.31 = 6850 Block Accesses With Index = log(6850) = 12.742 = 13 Without Index = log(200000) = 17.609 = 18

-- Oct 14 In-Class Exercise Thread

 Blocks for 1,000,000 tuples = 200,000 
 Bytes for 200,000 blocks = 819,200,000
 Index records per block (4096/28)= 146
 Index file blocks (1,000,000/146)= 6849  
 Index file bytes total = 218053504
 with index no. of block accesses = log base 2(6849)= 13
 without index no. of block accesses =log base 2(200,000)= 18

(Edited: 2020-12-13)

Blocks for 1,000,000 tuples = 200,000 Bytes for 200,000 blocks = 819,200,000 Index records per block (4096/28)= 146 Index file blocks (1,000,000/146)= 6849 Index file bytes total = 218053504 with index no. of block accesses = log base 2(6849)= 13 without index no. of block accesses =log base 2(200,000)= 18

-- Oct 14 In-Class Exercise Thread

 Suppose R had 1,000,000 tuples and 5 fit into a block of 4096 bytes.
 How many blocks and bytes does R take to store?
 1 000 000 / 5 = 200 000  blocks  
 200 000 * 4096 = 819 200 000 bytes

 If the key is 20 bytes long and the record pointer 8 bytes long, approximately how many index records can fit in a block?
 4096 / 28 = 146 records

 If we have a dense index on R, how many block and bytes would the index file take?
 1 000 000 / 146	= round_up(6849) = 6850 blocks
 6850 * 4096 = 28057600 bytes

 If we use binary search to do look ups how many block accesses would we need with and without the index?
 without index: log(200 000) / log(2) = 17.6096404744 = 18
 with index: log(6850) / log(2) = 12.6838718686 = 13

Suppose R had 1,000,000 tuples and 5 fit into a block of 4096 bytes. How many blocks and bytes does R take to store? 1 000 000 / 5 = 200 000 blocks 200 000 * 4096 = 819 200 000 bytes If the key is 20 bytes long and the record pointer 8 bytes long, approximately how many index records can fit in a block? 4096 / 28 = 146 records If we have a dense index on R, how many block and bytes would the index file take? 1 000 000 / 146 = round_up(6849) = 6850 blocks 6850 * 4096 = 28057600 bytes If we use binary search to do look ups how many block accesses would we need with and without the index? without index: log(200 000) / log(2) = 17.6096404744 = 18 with index: log(6850) / log(2) = 12.6838718686 = 13