search

blueworrybear / DataBaseProject1

1 stars 0 forks source link

關於stage 3 #20

Closed kevinLoe closed 12 years ago

kevinLoe commented 12 years ago

先舉例 B+ tree SELECT name FROM employee WHERE ID > 100 這個指令用B+ tree應該是不會很困難，我的想法是leaf node有數個data object(以這個例子來說，attribe有ID和reference(指到這個ID的 tuple，可能存在disk))，以及一個reference(指向下一個leaf node)。所以照這樣說是要先判斷WHERE clause，再把table檔案全部讀取出來建立tree結構，有幾個問題

  1. 所以每一個SELECT指令進來，都重新建立B+tree資料結構？這樣感覺好像沒有比之前的快，若一堆指令進來。
  2. WHERE比較的東西若是 Dept = 'CS' 這樣，那是按照字母順序建立tree嗎？
  3. WHERE若是 e.Dept = d.Dept ，這種情況要怎麼建立B+tree?
  4. 若是照我上面說的，data object的reference指向的是一個tuple，但是我們好像是把所以value存在table_content裡，這要怎麼連結在一起？ 這是我目前在想怎麼做遇到的問題，大家可以一起想，早點寫完才能早點做project 2(這東西不該有啊～～～)。
kevinLoe commented 12 years ago

http://use-the-index-luke.com/sql/where-clause/searching-for-ranges/greater-less-between-tuning-sql-access-filter-predicates 這裡有講到WHERE clause裡的兩個equation，如何決定排序的先後？以及一些data structure。

subsevenx2001 commented 12 years ago

1.應該是一開就建好，存成檔案，MySQL是這樣做的 2.我覺得應該是照LexicalOrder，當然轉成字碼用字碼排序也可以 3.這種情況B樹應該不適用，遇到這種情形可能就Scan其中一方的BTree把所有的值都丟到另一個table的BTree做搜尋，雖然感覺沒效率，但是跟暴搜O(n*m)比還是比較好一點 (O(nlogm)) 4.可不可以直接指Primary Key? 因為PK可以直接代表一個Tuple而不會有撞值的問題

ps.其實我在想，如果一開始INSERT的資料沒有PK，我們可不可以依照被INSERT的順序偷偷給他放上一個PK(0,1,2....)這樣，我們如果要做B+樹任何種類的資料都可以直接ref到PK (但是比對資料重複就只能一個欄位一個欄位比了...)

Data Object-->PK-->Tuple 這樣