Tôi khá mới đối với cơ sở dữ liệu, vì vậy hãy tha thứ cho tôi nếu đây là một câu hỏi ngớ ngẩn.Cơ sở dữ liệu về độ phức tạp của truy vấn cơ sở dữ liệu
Trong cơ sở dữ liệu hiện đại, nếu tôi sử dụng chỉ mục để truy cập một hàng, tôi tin rằng điều này sẽ là O (1) phức tạp. Nhưng nếu tôi làm một truy vấn để chọn một cột khác, nó sẽ là O (1) hoặc O (n)? Có phải cơ sở dữ liệu phải lặp qua tất cả các hàng, hay nó xây dựng một danh sách được sắp xếp cho mỗi cột?
Thực ra, tôi cho rằng truy cập dựa trên chỉ mục sẽ là O (log (n)), bởi vì bạn vẫn sẽ tìm kiếm thông qua tổ chức B-Tree-esque để truy cập vào hồ sơ của bạn.
Bạn có chỉ mục. Các chỉ mục được nhóm được sắp xếp vật lý trên đĩa, bạn chỉ có thể có một bảng trên mỗi bảng. Unclustered indexes được sắp xếp hợp lý và bạn có thể có nhiều trong số đó (cẩn thận không lạm dụng nó, nó có thể làm chậm các hành động viết). Nếu không có chỉ mục trên cột của bạn thì tôi tin rằng đó là hàng cũ tốt theo phương pháp hàng.
Chỉ mục là mỗi cột, vì vậy nếu bạn sử dụng mệnh đề where trên cột không được lập chỉ mục, nó sẽ thực hiện một cái gọi là tablescan là O (n).
Để trả lời câu hỏi theo nghĩa đen của bạn, có nếu không có chỉ mục trên cột, công cụ cơ sở dữ liệu sẽ phải xem xét tất cả các hàng.
Trong trường hợp thú vị hơn khi chọn nhiều cột, cả có và không có chỉ mục, tình hình trở nên phức tạp hơn: Nếu Trình tối ưu hóa truy vấn chọn sử dụng chỉ mục, thì trước tiên nó sẽ chọn các hàng dựa trên chỉ mục và sau đó áp dụng một bộ lọc với các ràng buộc còn lại. Do đó làm giảm hoạt động lọc thứ hai từ O (số hàng) thành O (số hàng được chọn theo chỉ số). Tỷ lệ giữa hai số này được gọi là chọn lọc và một số liệu thống kê quan trọng khi chọn chỉ mục để sử dụng.
Có nhiều loại chỉ mục khác nhau, các kế hoạch thực thi khác nhau và các triển khai khác nhau cho các cơ sở dữ liệu khác nhau. Hầu hết mã cơ sở dữ liệu quan hệ là trong thuật toán tối ưu hóa tìm kiếm. Không có một câu trả lời duy nhất cho câu hỏi của bạn. Bạn có thể sử dụng một công cụ để trực quan hóa kế hoạch thực hiện khi bạn muốn biết truy vấn sẽ được thực hiện như thế nào.
đúng, nhưng vẫn gần đúng (và những gì anh ấy tìm kiếm) là: O (log (n)) khi được lập chỉ mục và O (n) khi không phải là – Javier
Điều đó đúng, nhưng các chỉ mục không phải lúc nào cũng là yếu tố hạn chế nhất trong các truy vấn.Trong một số trường hợp, bạn có thể không nhận thấy sự khác biệt giữa việc sử dụng chỉ mục hay không. – Paco
@Paco: đó là công cụ tốt nhất để trực quan hóa kế hoạch thực hiện? – Miranda
Tôi không biết câu trả lời, nhưng hãy nhớ rằng ký hiệu big-O chỉ cung cấp cho bạn chỉ báo hiệu suất cho các kích thước tập dữ liệu tùy ý lớn.
Ví dụ: nút cổ chai cho hiệu suất cơ sở dữ liệu thường là tìm kiếm đĩa. Do đó, hiệu suất được tăng lên rất nhiều nếu bộ dữ liệu làm việc có thể được lưu giữ trong bộ nhớ. Ký hiệu Big-O sẽ không cho bạn biết bất cứ điều gì về các tối ưu hóa như vậy, bởi vì chúng chỉ thích hợp cho các tập hợp dữ liệu hữu hạn.
B-cây không mang lại O (logN), đó là độ phức tạp của cây nhị phân.
Một cây B được tổ chức sao cho nó có toàn bộ khối trên mỗi nút, do đó khi một nút được tìm thấy, một thao tác I/O có thể đọc toàn bộ khối.
Với số lượng mục trên mỗi nút = yếu tố chặn (# bản ghi/khối) {bfr}, tìm kiếm được tối ưu hóa cho B-Tree sẽ mang lại các hoạt động I/O thay cho O (log bfr ÷ 2 +1 N) O (N) hoạt động I/O tìm kiếm một bản ghi bằng khóa.
Xin lỗi nếu tôi yêu cầu bạn ra khỏi màu xanh, nhưng có một cuốn sách mà bạn có thể đề nghị tôi, nơi tôi có thể tìm thấy loại thông tin như vậy? – jackb
Hãy nhớ rằng O (log_k n) = O (nhật ký n/log k) = O (log n) cho bất kỳ hằng số k nào, vì vậy về mặt kỹ thuật, các tra cứu B-Tree thực hiện thời gian O (log n). Tuy nhiên, chúng nhanh hơn rất nhiều so với cây nhị phân, nhưng chỉ bởi một yếu tố không đổi. – cfstras
Ngoại trừ chỉ mục băm, trong đó nó là O (chiều dài chuỗi-chuỗi) –