# Secondary composite-key pages access

we have this relation
Store: [SID, City, EID]
Employee: [EID, Name, Salary, SID]
Article: [AID, Name, Producer, Price]
Inventory: [AID, SID, Count]
Invoice: [IID, SID, Customer]
Item: [IID, SID, AID, Count]

Store.EID is a foreign key referencing Employee.EID and designates the store manager. Employee.SID is a foreign key referencing Store.SID and describes in which store this employee is employed. The inventory table stores (with foreign keys) how many articles (AID) are in stock at which store (SID). An invoice is generated at a store (SID) and consists of multiple items, where each item is composed of an article (AID) and a count.

The Employee table contains 20 000 employees, of which exactly two tuples t into one page. Each employee has a (uniformly distributed) salary between 20 000 and 100 000. There are 10 stores, each with the same amount of employees. The Employee table has two secondary composite-key indices on (Salary,EID) and (EID,Salary). Both indices are B+ trees with a height of h and each leaf can store 5 references to pages.

The question is Which index requires less page accesses for the query select * from Employee where EID = 5 and Salary > 60000?

So I know that the (EID, Salary) is better to use here, since the EID is unique and it will go to the EID = 5 and then find his salary, however, I find it a little bit confusing because actually, we have one access to the EID 5 then the condition will be checked and we will either get this employee or not. So how can I calculate the costs of each in order to compare between them?

• So for the index (EID, Salary) you have (in the worst case) 1 page access to read the data plus the ones you need to go through the B-tree (that should be I guess h). And how many will you have (on average and worst case) for the index (Salary, EID) ? – ypercubeᵀᴹ Nov 10 '18 at 20:53
• I do not know how many employees have a salary bigger than 60000 but I know that each one of them earns different salary of the other person so none of them has the same salary, however between 60000 and 100000 there is 40000 so in worst case all the employees have a salary bigger than 60000 so 20000 employees and since each page can contain 2 tuples so we have 10000 pages in worst case I suppose. – Dania Nov 10 '18 at 21:15