Báo cáo " Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian "

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:8

Thêm vào BST

Báo xấu

207
lượt xem 33
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian . Bài báo này đề cập đến khái niệm và một số phương pháp đánh chỉ mục trong cơ sở dữ liệu không gian (spatial datadase – SDB). Là một trong những mô hình cơ sở dữ liệu được quan tâm hiện nay, SDB cho phép xử lý các đối tượng dữ liệu không gian. Một trong những bài toán cơ bản của SBD chính là việc tối ưu hóa quá trình dữ liệu và truy vấn...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo " Ứng dụng cây QR tạo chỉ mục trong cơ sở dữ liệu không gian "

Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 ng d ng cây QR t o ch m c trong cơ s d li u không gian Dư Phương H nh* Trư ng ð i h c Công ngh , ð i h c Qu c gia Hà N i, 144 Xuan Th y, Hà N i, Vi t Nam Nh n ngày 7 tháng 01 năm 2011 Tóm t t. Bài báo này ñ c p ñ n khái ni m và m t s phương pháp ñánh ch m c trong cơ s d li u không gian (spatial datadase – SDB). Là m t trong nh ng mô hình cơ s d li u ñư c quan tâm hi n nay, SDB cho phép x lý các ñ i tư ng d li u không gian, ch ng h n d li u b n ñ , d li u multimedia... ñ t ñó có th xây d ng nên nh n g kho d li u không gian. M t trong nh n g bài toán cơ b n trong SDB chính là vi c t i ưu hoá quá trình lưu tr d li u và truy v n. Trong bài báo này, chúng tôi s trình bày v hai ph ương pháp ñánh ch m c ñi n hình liên quan ñ n v n ñ ñánh ch m c gi i bài toán trên, R-tree và Q-tree. T ñó, ý tư ng k t h p hai phương pháp này s chính là ñ nh hư ng ch ñ o cho vi c t i ưu hoá lưu tr d li u cũng như truy v n trên cơ s d li u không gian. T khóa: Spatial database, spatial indexing, R-tree, Q-tree, QR-Tree. Warehouse (SDW). Các nghiên c u trên lĩnh 1. Gi i thi u∗ v c này ñã thu ñ ư c r t nhi u thành t u, tuy Các nghiên c u v công ngh cũng như ng nhiên cũng còn không ít khó khăn và thách th c d ng trong lĩnh v c cơ s d li u (CSDL) ñang ñòi h i ph i có các gi i pháp m i. tăng trư ng v i m t s c m nh ñ áng kinh ng c. Bài báo này trình bày m t phương pháp Cùng v i s tăng trư ng nhanh chóng c a ñánh ch m c trên SDB, là s k t h p gi a hai lư ng thông tin cũng như s ñ a d ng v th lo i phương pháp ñánh ch m c ph bi n là Q-tree thông tin c n lưu tr và x lý, chúng ta ngày và R-tree, k t h p các ưu ñi m c a c hai càng nh n ra nh ng h n ch c a các H qu n tr phương pháp này cũng như gi m thi u như c cơ s d li u quan h truy n th ng, và nhu c u ñi m c a chúng, nh m tăng hi u su t th c thi c n ph i có các h q u n tr cơ s d li u v i các các phép toán. d ch v phù h p chính là y u t t húc ñ y nh ng nghiên c u m i trong lĩnh v c này. M t trong các mô hình cơ s d li u ñư c quan tâm nh t 2. Khái ni m cơ b n hi n nay chính là mô hình cơ s d li u không Ph n này s ñư c t p trung trình bày nh ng gian - Spatial DataBase (SDB) x lý các ñ i khái ni m cơ b n liên quan ñ n mô hình SDB. tư ng d li u không gian, ch ng h n d li u b n ñ , d li u multimedia... và m r ng hơn 2.1. D li u không gian n a là kho d li u không gian - Spatial Data Thu t ng d li u không gian (spatial data) _______ ñư c s d ng theo nghĩa r ng, bao g m các ∗ ð T: 84-4-37547813. E-mail: hanhdp@vnu.edu.vn 14
15 D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 ñi m ña chi u, các ñư ng th ng, hình kh i... và h p c a các ñ o n th ng; qu c gia, thành ph có các ñ i tư ng hình h c nói chung. M i ñ i th ñư c bi u di n dư i d ng các hình ña giác... tư ng d li u này chi m m t vùng không gian (spatial extent) ñư c ñ c trưng b i hai thu c 2.2. Các phương pháp truy v n ph bi n trên tính v trí (location) và biên (boundary). Dư i d li u không gian góc nhìn t m t h qu n tr cơ s d li u, có th a) Truy v n theo ph m vi không gian phân chia d li u không gian thành hai ki u: d (Spatial range queries): li u ñi m (point data) và d li u vùng (region data) [1] Gi s chúng ta có yêu c u truy v n “ðưa ra tên t t c các thành ph xu t hi n trong D li u ñi m; V i ki u d li u này, không ph m vi 1000km quanh Hà N i” ho c “ðưa ra gian ng v i m t ñi m ñư c ñăc trưng b i t a tên các con sông ch y qua khu v c B c B ”. ñ c a nó; theo tr c giác thì nó không chi m M t truy v n theo ki u này s ch a m t vùng m t vùng không gian hay m t ñơn v th tích liên ñ i (v i các thu c tính v trí và biên t ương nào c . D li u ñi m là t p h p các ñi m trong ng), và k t q u tr v s là m t vùng bao trùm không gian nhi u chi u, ñ ư c lưu tr trong ph m vi không gian ñ ã ch ra trong truy v n CSDL d a trên các t a ñ ñ ư c tính toán tr c ho c là m t t p h p các vùng thu c trong ph m ti p, ho c ñư c sinh ra nh quá trình chuy n vi không gian ñã ch ra trong truy v n. Ki u hóa d li u thu ñ ư c t các phép ño khi n cho truy v n theo ph m vi ñư c s d ng trong các vi c lưu tr và th c hi n truy v n tr nên d ng d ng trên nhi u lĩnh v c ña d ng bao g m dàng hơn. Ch ng h n Raster data là m t ví d truy v n quan h , truy v n GIS, truy v n d li u ñi m ñư c lưu tr tr c ti p thông qua CAD/CAM [1] các bit maps ho c pixel maps (ch ng h n như nh v tinh, ho c phim ñi n não ñ 3 chi u, …). b) Truy v n d a trên các láng gi ng g n Trong khi ñó, feature vectors data ñư c lưu tr nh t (Nearest neighbor queries): thông qua các d li u ñư c trích ch n, chuy n V i m t yêu c u ch ng h n như “ðưa ra tên ñ i t m t ñ i t ư ng d li u ñi m (thu ñư c t 19 thành ph g n Hà N i nh t”, chúng ta nh, văn b n...). Có th th y r ng, s d ng các thư ng mu n k t qu tr v ñư c s p x p theo d li u ñã ñư c bi u di n ñ tr l i các truy v n th t nào ñó v kho ng cách. ðây là d ng truy luôn d dàng hơn s d ng nh ho c ký hi u v n ñ ư c s d ng nhi u nh t ñ i v i d li u nguyên b n. multimedia. Trong trư ng h p này, d li u D li u vùng: ñư c xác ñ nh d a trên t p multimedia (ch ng h n là nh) ñ ư c bi u di n các vùng không gian (spatial extents), trong ñó dư i d ng m t ñi m, và d li u tương t c n m i vùng ñư c ñ c trưng b i hai thu c tính v tìm ki m ñ ư c tính toán theo kho ng cách g n trí và biên. D li u vùng ñ ư c l ưu tr trong nh t t i ñi m bi u di n ñ i tư ng truy v n. [1] CSDL như m t ñ i tư ng hình h c ñơn gi n, c) Truy v n liên k t không gian (Spatial join x p x ñúng v i ñ i tư ng d li u th c s . Vi c queries): mô t các phép x p x ñó ñư c ñ c t thông qua Các yêu c u truy v n thông thư ng thu c vector d li u, ñư c xây d ng t các ñi m, các d ng này là “ðưa ra các thành ph cách nhau ño n th ng, các hình ña giác, hình c u, hình không quá 200km” ho c “ðưa ra tên các con ng... R t nhi u ví d d li u vùng ñư c ñ ưa ra ph g n h ”. Các d ng truy v n này thư ng r t trong các ng d ng ñ a lý, ch ng h n ñư ng xá, m t th i gian ñ tính toán. N u chúng ta xem sông ngòi có th ñư c bi u di n dư i d ng t p xét m t quan h trong ñó m i m t ph n t là
16 D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 m t ñi m bi u di n m t thành ph ho c m t cái th . Hi n chưa có ñư c s nh t trí r ng c u trúc h thì truy v n trên có th ñư c th c hi n b ng ñánh ch s nào là t t nh t, tuy nhiên R tree là phép n i quan h này v i chính nó v i ñi u c u trúc ñư c s d ng r ng rãi và ñã xu t hi n ki n n i ch ra kho ng cách gi a hai ph n t trong các b n DBMS thương m i, do tính ñơn tương ng. ðương nhiên, n u các thành ph và gi n và kh năng áp d ng cho c hai d ng d h ñ ư c bi u di n chi ti t hơn và có vùng li u ñi m và vùng. không gian c a chúng, ng nghĩa c a truy v n (chúng ta tìm ki m hai thành ph mà trung tâm 3.1. Q - tree c a chúng cách nhau 200km hay hai thành ph Q - tree [3] là phương pháp ñánh ch s d a mà biên c a chúng cách nhau 200km) và vi c trên ñư ng cong Space-Filling Curves ñ s p th c thi truy v n ñ u tr nên ph c t p hơn x p các ñi m d li u. Vi c ñ ánh ch s ñư c nhi u. [1] th c hi n d a trên vi c p hân chia không gian d li u m t cách ñ quy, nhưng khác v i R-tree, 3. Q-Tree, R-Tree và QR-Tree phương pháp này ñư c th c hi n ñ c l p ñ i v i t p d li u t h c s . Space-Filling Curves R t nhi u c u trúc ñánh ch s trên CSDL ñư c xây d ng d a trên gi t hi t r ng m i giá không gian ñã ñ ư c ñ xu t, m t s ñư c thi t tr thu c tính nào ñó ñ u có th bi u di n b i k ch y u dành cho t p d li u ñi m m c dù m t s bit xác ñ nh nào ñó g i là k bit, do ñó s chúng cũng có th áp d ng cho ki u d li u lư ng các giá tr thu c v cùng m t chi u d vùng. C u trúc index dành cho d li u ñi m có li u có th ñ t t i nhi u nh t là 2k. ð ñơn gi n, th k t i Grid files, HB tree, KD tree, Point hình v dư i ñây mô ph ng m t t p d li u 2- Quad tree và SR tree... Các ki n trúc khác như chi u m c dù th c t là phương pháp này có th Region Quad tree, R tree và SKD tree áp d ng áp d ng v i d li u có s chi u b t k ỳ. Hình v cho d li u vùng, tuy nhiên chúng cũng có th th nh t s d ng 2 bit ñ bi u di n giá tr thu c áp d ng cho d li u ñi m [2, 3]. tính; hình th hai s d ng 3 bit; và hình th ba Region Quad tree (Q-tree) và R-tree là hai là ñư ng cong Hilbert v i 3 bit. hư ng ti p c n khác nhau và có r t nhi u bi n Hình 1. Space-Filling Curves.
17 D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 Trên ý tư ng này, Q-tree là phương pháp và 11 (góc ph n tư bên ph i phía trên). Trên phân chia m t cách ñ quy không gian d li u hình v , chúng ta có th th y r ng n u không thành các góc ph n tư, ñ ư c minh h a trong gian d li u không ñ ư c phân b m t cách ñ i hình v 3: Trong c u trúc này, m i nút có 4 con x ng thì cây Q-tree s b l ch, b i vì Q-tree l n lư t ng v i các góc ph n t ư 00 (góc ph n không ph i là m t c u trúc cây cân b ng, do ñó tư bên trái phía dư i), 01 (góc ph n tư bên trái trên nh ng t p d li u l n, hi u su t truy c p d li u s kém hi u qu . phía trên), 10 (góc ph n t ư bên ph i phía dư i) Hình 2. C u trúc ñánh ch m c Q-tree. M t m t khác, trong các ng d ng ñòi h i hình 4. ðơn gi n nh t, hình kh i t hư ng ñư c vi c lưu tr d li u có tính ch t liên t c (ch ng s d ng là hình ch nh t nh nh t ch a d li u h n d li u v m t ñ i tư ng chuy n ñ ng) thay (Minimum Bounding Rectangle – MBR). Như vì các d li u xác ñ nh, chúng ta g p p h i m t v y, chính các MBR ñư c lưu tr trên c u trúc v n ñ r t khó ñ cân nh c b i vì: vi c s d ng cây ch không ph i b n thân d li u. CÁc nút cây Q-tree có ñ sâu càng l n thì ñ chính xác không ph i lá ñ ư c bi u di n b i c p (R, child- bi u di n d li u càng t t, tuy nhiên nó l i pointer) trong ñó R là MBR c a ñ i tư ng và khi n cho vi c xây d ng c u trúc này tr nên child-pointer là con tr tr t i nút con; các nút kém hi u qu trên c p hương di n không gian là ñư c bi u di n b i c p (R, obj-pointer) trong lưu tr và th i gian x lý các thao tác. ñó R là MBR c a ñ i tư ng và obj-pointer là con tr tr t i mô t chi ti t c a ñ i tư ng. M i nút trong cây tương ng v i m t trang b nh . 3.2. R-tree Và m c dù các MBR có th ch ng chéo lên R-tree là phương pháp phân chia không nhau, t c là các nút có th ch a d li u gi ng gian d li u thành các kh i có th l ng nhau nhau, nhưng m i ñ i tư ng d li u ph i ñư c ho c ch ng chéo lên nhau, ñư c minh h a trong lưu tr tr n v n trên m t nút lá.
18 D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 Hình 3. C u trúc ñánh ch m c R-tree. Chúng ta có th t h y R-tree là m t bi n th 1) T c ñ th c hi n xây d ng cây Q-tree c a B+ tree và nó là m t cây cân b ng. Truy nh hơn nhi u so v i R-tree b i vì vi c phân nhiên, do các MBR có th ch ng chéo lên nhau chia, r i l a ch n MBR, sau ñó chèn l n l ư t t ng nút vào R-tree là r t t n kém th i gian và s ch ng chéo này gia tăng khi lư ng d li u gia tăng nên c u trúc này có y u ñi m là kéo 2) Tuy nhiên vi c ñánh ch s theo Q-tree theo s gia tăng các truy c p tìm ki m không không phù h p v i các t p d li u l n do tính c n thi t. Thêm n a, chúng ta b t bu c ph i ti n không cân b ng c a nó. hành tìm ki m t i m i m c c a cây, ngay c C hai c u trúc này ñ u có các bi n th v i trong các trư ng h p không có (ho c có r t ít) r t nhi u c i ti n, tuy nhiên, chúng v n không ñ i tư ng d li u th a mãn yêu c u. th ñ c l p ñáp ng các ñòi h i v t c ñ th c thi c a các ng d ng th i gian th c. Như v y, 3.3. K t h p R-tree và Q-tree gi i pháp k t h p hai phương pháp này v i nhau (hybrid) ñ t n d ng ưu ñi m c a c hai Q-tree và R-tree ñ u có các ưu ñi m và phương pháp, b tr cho nhau dư ng như là như c ñi m riêng, ph thu c c vào các tình m t gi i p háp h p lý. Hình v 5 minh h a vi c hu ng và các thao tác khác nhau. s d ng QR-tree. Hình 4. C u trúc ñánh ch m c s d ng QR-tree.
19 D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 4. T i ưu hoá quá trình ñánh ch m c phương pháp QR-Tree ñ gi i quy t v n ñ trên. 4.1. Các công trình liên quan Trong phương pháp này, R-Tree ñư c áp d ng không ch m c lá c a Q-Tree mà còn R t nhi u các c i ti n v k thu t ñánh ch k t h p v i c các nút không ph i là lá c a Q- m c ñã ñ ư c công b nh m tăng hi u qu th c Tree. ði u này có nghĩa là n u m t ñ i t ư ng thi truy v n. thu c v nhi u vùng d li u khác nhau (như D. Pfoser[4] ñã ñưa ra STR-tree (Spatio- trư ng h p 6 và 7 trong hình 5) thì m c cha c a Temporal R-tree) và TB-tree (Trajectory- nó s ñ ư c xem xét li u nó có th ch a toàn b Bandle tree) và ch ra r ng hai c u trúc này ñ i tư ng d li u này hay không. Vi c ki m tra hi u qu hơn h n so v i các c u trúc trư c ñó này c ti p t c cho ñ n g c (root). M t ñ i trong lĩnh v c lưu tr các ñ i tư ng chuy n tư ng O ñư c ñ nh nghĩa là thu c v vùng ñ ng. Tao và Papadias [5] ñ xu t MV3R-tree không gian con S n u O hoàn toàn n m trong S (Multi Version 3D R-tree), là s k t h p gi a và S là vùng không gian con nh nh t ch a O. B-tree và 3D-tree. Như v y, các ñ i tư ng n m t ương ñ i xa nhau QR-Tree ñ ư c ñ xu t b i Manolopoulos, s ñư c lưu tr trên các nhánh khác nhau, nh Y. năm 1996 là c u trúc g m hai t ng: áp d ng ñó gi m thi u s ch ng chéo gi a các MBR. Q-tree t ng th nh t ñ phân chia không gian Lúc này, m t ñ i tư ng c th ñ ư c g n m t d li u, sau ñó t ng th hai áp d ng R-tree trên ch s duy nh t nên hi u su t c a quá trình chèn các vùng d li u ñã ñư c chia nh b i Q-tree. d li u vào cây s tăng lên (do vi c th i gian Cũng v i phương pháp k t h p R-tree và Q- xây d ng l i cây ñư c rút ng n); m i phép toán tree, K. Chakarabarti và S.Mehrotra [6] ñã ñưa s ñ ư c th c hi n trên m t t p các vùng d li u ra m t c u trúc cây lai ñ ư c s d ng cho vi c t i thi u (do không có ch a các d li u l p sinh ñánh ch m c v i d li u có s chi u l n. Yuni ra do s ch ng chéo các vùng không gian) nên Xia và Sunil Prabhakar [7] ñã ñ xu t Q+Rtree vi c truy c p d li u s nhanh hơn, th i gian áp d ng trong các bài toán ñ i tư ng chuy n ñáp ng yêu c u truy v n ñư c rút ng n. ñ ng, c i ti n hi u su t th c t hi trong c hai C th hơn, Q-tree ñ ư c s d ng ñ p hân thao tác c p nh t và truy v n. chia thô toàn b d li u và lưu tr trong b nh chính. R-tree s ñư c s d ng ñ duy trì c u 4.2. Phương pháp QR-Tree c i ti n trúc logic c a cây, ñ ư c th hi n dư i d ng m t QR-Tree m c dù có ưu ñi m rõ ràng nhưng b ng ch s mà m i dòng trong ñó tương ng nó v n t n t i ñi m y u. Nhìn vào hình v 1.5, v i m t nút c a cây R-tree. M i cây R-tree có th th y rõ ràng r ng hai ñ i tư ng 6 và 7 tương ng v i các nút c a Q-tree ñư c lưu tr xu t hi n t i c hai nút. Như v y m i khi c n trong cùng m t b ng ch s . M i dòng trong c p nh t n i dung, xóa ho c truy v n d li u, b ng này có ch a m t thu c tính có tên chúng ta v n ph i th c hi n l p l i công vi c ‘Partition’ ñ ch ra vùng không gian con có t t c hai nhánh ch a 6 và 7, gây nh hư ng t i ch a nút ñó. B ng cách t ch c như v y, m t t c ñ th c thi c a các.phép toán. Phương pháp cây R-tree tương ng v i m t vùng không gian QR c i ti n ñư c xây d ng d a trên n n t ng là con Q-tree có th ñư c tham chi u t i nh vào
20 D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 giá tr c a t hu c tính ‘Partition’ c a các nút c a L i c m ơn cây Q-tree. ð chèn m t ñ i tư ng v i MBR Công trình này ñ ư c tài tr m t p h n t ñ c a nó, trư c tiên ta thêm vào b ng d li u, l y tài mang mã s : QC.08.03, ð i h c Qu c gia ra ID c a ñ i tư ng này r i g i m t hàm th c Hà N i. hi n vi c ñ nh v v trí c a nó trên Q-tree; v trí tìm ñư c có th là nút g c, nút lá ho c m t nút cha trong cây. D a vào v trí này, k t h p v i Tài li u tham kh o b ng ch s ta có th truy c p t i cây R-tree và [1] Raghu Ramakrishnan/Johannes Gehrke. xác ñ nh ñư c root c a cây R-tree ñó. C như Database Management Systems, McGraw Hill, v y, quá trình l p l i trên các nhánh con c a cây 2sd edition. t i khi g p nút lá có tri n v ng nh t thì ti n [2] Manolopoulos, Y. (1996). QR-tree-a hybrid spatial data structure, Proceedings of the 1st hành chèn MBR và ID c a ñ i tư ng, và cu i International Conference on Geographic cùng là cây R-tree n u c n thi t. Information Systems in Urban, Regional and Environmental Planning, Samos Island, Greece, pp. 3–7. 5. K t lu n [3] Rauber A., Tomish P., Riedel H., and Kouba Z. Integrating Geo-Spatial Data into OLAP SDB ñã và ñ ang thu hút ñư c nhi u nghiên Systems Using a Set-based Quad-Tree Representation. In Proc. of the 4th Int. Conf. c u trong th i gian g n ñây, nh t là khi nh ng onInformation technology for Balanced d ch v trong lĩnh v c GIS hay multimedia Automation Systems in Production and Transportation, BASYS, 2000. ngày càng phát tri n. V i nh ng d li u có yêu [4] D. Pfoser, C. S .Jensen, and Y. Theodoridis. c u lưu tr l n như v y, bài toán t i ưu hoá quá Novel approaches in query processing for trình ñánh ch m c cho nh ng d li u ñó là m t moving objects. Proceedings of the 26th bài toán th i s và liên quan m t thi t ñ n hi u International Conference on Very Large Databases (VLDB), September 2000. năng c a nh ng truy v n trong SDB. D a trên [5] Papdias D., Kalnis P., Zhang J., and Tao Y. hai phương pháp ñánh ch m c R-Tree, Q-Tree Efficient OLAP Operations in Spatial Data và phương pháp lai QR-Tree k t h p nh ng ưu Warehouse. In Proc. of the 6th International Symposium on Spatial and Temporal Databases, ñi m t hai phương pháp trên, chúng tôi ñã ñ SSTD, 2001. xu t c i ti n phương pháp ñánh ch m c QR- [6] K. Chakarabarti and S.Mehrotra. The hybrid Tree ñ gi m thi u hơn n a s ch ng chéo tree: An index structure for high dimensional trong lưu tr d li u nh m nâng cao hi u năng feature spaces. Proceedings of he Fourteenth th c thi truy v n và các phép toán khác. Nh ng International Conference on data engineering (ICDE’99), 1999. k t qu th c nghi m trong th i gian t i c a [7] Yuni Xia, Sunil Prabhakar. Q+Rtree: Efficient nhóm tác gi s cho phép ki m ch ng nh ng ưu Indexing for Moving Object Databases. In Proc. ñi m thu ñư c t nh ng ñ xu t lý thuy t c a of the 8th International Symposium on Spatial and Temporal Databases, SSTD, 2004. phương pháp này.
21 D.P. Hạnh / Tạp chí Khoa học ĐHQGHN, Khoa học Tự nhiên và Công nghệ 27 (2011) 14-21 Using QR-Tree for Spatial Database Indexing Du Phuong Hanh University of Engineering and Technology, VNU, 144 Xuan Thuy, Hanoi, Vietnam This paper presents several indexing methods for the spatial datawarehouse (SDW). Actually, SDW is considered as one of most interresting models for manipulating the sptial entities like digital maps, multimedia,… For the SDW, the query optimization is very important due of the mass of spatial data.Thus, this paper investigates the two modern techniques, Q-Tree and R-Tree, for indexing the spatial data in order to improve the performance of the query optimizer. Then, the hybrid approach using QR-Tree will be mostly considered for optimizing the data storage query optimization for spatial database.