Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    1 [Kinh nghiệm]Nói về B++ tree on Sun Jan 29, 2012 10:57 pm

    Admin


    Quản trị viên
    Quản trị viên
    Các tài liệu về B+ tree toàn bằng tiếng Anh (Kể cả của thầy và cả trên Internet, có google cũng không có bản tiếng Việt nào nên hồn) thôi thì gõ một ít ra đây để tiện trao đổi. Một số bạn có hỏi gì thì hỏi lên diễn đàn, đừng có bom vào thùng thư của tôi, mỗi ngày nhận tới vài trăm thư, nên tôi chỉ đọc những thư quan trọng thôi còn lại là AutoDelete, nên hết sức thông cảm.
    Tiện thể nhắc luôn mấy cái anh chàng và cô nàng không chịu đọc kỹ, mà đã nhắc lại nhiều lần rồi là đã ở nhóm "Học viên DS" thì đừng có đòi tham gia vào nhóm khác (Thành viên đọc được mọi thứ) vì có tham gia vào thì sẽ đảo bit = 0 sẽ bị cấm không đọc được đâu. Đã nhắc đi nhắc lại rồi mà vẫn cứ lao đầu xin chết thì cũng lạ đấy nhé.

    Thôi năm mới nói tý cho vui, gõ một ít về bài học cho những người lười học thì lên đây đọc. Mà nói thật là nếu cứ học kiểu này có khi phải thuê bạn Hải Yến ở trường Mầm Non Hoa Phượng Đỏ học hộ và thi hộ mất thôi.

    B+ Tree là một cấu trúc dữ liệu dạng cây ‘đa phân cân bằng’. Cấu trúc một node của nó thường được chia làm nhiều phần. Cây được tổ chức với một qui tắc nhất định được tạo ra từ đầu. Thường thì giá trị của các node tăng dần từ trái qua phải, node con bên trái sẽ chứa giá trị nhỏ hơn node con bên phải...

    [You must be registered and logged in to see this image.]

    B + Tree là một sự tổng quát hóa của cây nhị phân tìm kiếm (BST). Sự khác biệt chính giữa chúng là số lượng node con của B+Tree nó sẽ nhiều hơn chứ không bị giới hạn bởi hai phần tử như của cây nhị phân tìm kiếm. Mục tiêu ở đây là làm sao để giảm tối đa số lần truy xuất các thiết bị ngoại vi (ở đây là đĩa). Tại bất cứ thời điểm nào chúng ta sẽ thử định vị những bản ghi, chúng ta muốn độ cao của cây đa phân này phải là nhỏ nhất để giảm chi phí tìm kiếm, để đạt được mục tiêu này thì số lượng nhánh trong cây phải lớn.

    Nếu B+Tree có bậc là m thì môt node của nó sẽ có tối đa m nhánh con và có m-1 khóa để tìm kiếm.

    • Các record chỉ được lưu ở nút lá của cây

    • Tất cả các nút (ngoại trừ nút gốc) có tối thiểu là m/2 (ở đây phép chia nguyên làm tròn về phía trên, nếu lẻ) và tối đa là m nhánh con.

    • Nút gốc và lá phải ít nhất có 2 con.

    • Bên trong một node lưu giá trị tìm kiếm, một vài khóa được sử dụng như những “người chỉ đường” cho quá trình tìm kiếm. Những khóa này cần phải được sắp xếp theo môt thứ tự thống nhất trừ trước (tăng dần từ trái qua phải).

    • Tùy thuộc vào kích thước của một record so với kích thước của một khóa thì node lá của B+Tree bậc m có thể lưu nhiều hơn hoặc ít hơn m records. Thông thường kích thước của một node là bội số của một khối dữ liệu trong ổ đĩa (bên windows mặc định là 512byte).

    • Các node lá của cây thường được liên kết với nhau để tạo thành một danh sách liên kết, điều này nhằm mục tiêu là để không phải duyệt trở lại node gốc trong quá trình duyệt tìm kiếm.

    Ví dụ một cây B+Tree:
    [You must be registered and logged in to see this image.]


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    2 Re: [Kinh nghiệm]Nói về B++ tree on Sun Jan 29, 2012 11:12 pm

    Admin


    Quản trị viên
    Quản trị viên
    Các đề tham khảo về câu dạng này:
    1. Hãy cho biết kết quả của các thao tác sau khi thực hiện tren cây B-Tree với bậc m=5(vẽ cây minh họa từng bước) khi lần lượt thêm các khóa sau vào cây: 15, 35, 26, 18, 22, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25, 11, 97, 48, 63, 78, 20.

    2. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 7, 67, 43, 45, 50, 99, 95, 70, 75, 55, 60, 8, 12, 5, 3, 20, 22, 15, 26, 65, 80,30, 40,19, 57, 89. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.

    3. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 13, 5, 8, 11, 65, 1, 45, 33, 87, 21, 4, 55, 20, 34, 39, 32, 90, 56, 43, 68, 59, 49, 23, 47, 14, 24. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.

    4. a. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 5, 34, 22, 1, 32, 6, 7, 23, 45, 56, 3, 89, 51, 59, 33, 50, 9, 46, 83, 11, 19, 65, 49, 43, 38, 17, 92, 27, 82. Trình bày tiến trình khi lần lược thêm từng khóa trên vào cây.
    b. Cho biết kết quả cuối cùng cua B+-tree lần lượt thêm các khóa ở câu a.

    5. a Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 20, 78, 63, 48, 97, 11, 25, 45, 24, 38, 32, 8, 27, 46, 13, 42, 22, 18, 26, 35, 15, 82, 92, 3, 51. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.
    b. Cho biết kết quả cuối cùng cua B+-tree (m=5) tuong ứng với cây B-Tree ở câu a.

    6. a.Cho cây B-Tree với bậc m=6. Lần lượt thêm các khóa sau vào cây: 57, 21, 34, 15, 58, 47, 94, 17, 46, 11, 49, 86, 82, 20, 99, 48, 95, 44, 55, 38, 63, 66, 59, 39, 78, 16, 68, 64, 90, 112, 135, 104 và 10. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.
    b.Cho biết kết quả cuối cùng cua B+-tree lần lược thêm các khóa ở câu a.

    7. a. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 56, -54, 84, 75, 48, 59, 83, -96, 67, -90, 85, 89, 90, 13, 9, 68, 25, 60, 5, 19, 52, 21, 28, 66, 45, 4, 50, 64, 24, 37, 47, -78, -76, 87, 2, 54, 81, 17, -42, 6, 74. Trình bày tiến trình khi lần lược thêm từng khóa trên vào cây.
    b. Trình bày tiến trình khi lần lược xóa khóa -42 và 25.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    3 Re: [Kinh nghiệm]Nói về B++ tree on Mon Jan 30, 2012 7:46 am

    thang_bk


    Thành viên cao cấp
    Thành viên cao cấp
    Đại ca đưa lời giải luôn nhé.


    ================
    Stay Hungry. Stay Foolish.

    4 Re: [Kinh nghiệm]Nói về B++ tree on Mon Jan 30, 2012 7:53 am

    HaiYen


    Thành viên cao cấp
    Thành viên cao cấp
    Theo em, đặc điểm quan trọng nhất của B tree là:
    1. Có các record, và các record chỉ được lưu ở nút lá của cây

    2. Khi chia nút ra, thì khác với cây B, là nút giữa được copy 1 lần đẩy lên trên. Tức là có 2 phiên bản giá trị khoá (1 ở lá và 1 ở nút con). Sở dĩ như vậy vì nút con không có record, nên nó được đẩy lên làm khoá tìm kiếm, còn nút lá vẫn là đầu mối quan trọng để tìm và liên kết với nhau.

    3. Các nút lá liên kết với nhau theo dạng xâu liên kết. Nên ta có thể tìm luôn trên lá mà không cần phải quay ngược lên trên để tìm (Theo lý thuyết). Tuy nhiên việc tìm trên lá sẽ mất nhiều thời gian hơn do truy cập bộ nhớ ngoài (Còn tìm trên cây là tìm trong RAM) nên khi thầy có hỏi đừng có ngốc nghếch mà bảo tìm trên lá nhanh hơn, kẻo lại bị đánh giá là ... chẳng hiểu gì cả.

    Thắng BK đã viết:Đại ca đưa lời giải luôn nhé.

    Cài Java vào đây thêm từng node vào nó sẽ thêm hộ, rồi chép ra:
    [You must be registered and logged in to see this link.]


    ================
    Nhà em cách 4 quả đồi
    Cách 3 con suối, cách đôi cánh rừng
    Nhà em xa cách quá chừng
    Em van anh đấy, anh đừng yêu em!...

    FaceBook của em

    5 Re: [Kinh nghiệm]Nói về B++ tree on Mon Jan 30, 2012 9:54 am

    Admin


    Quản trị viên
    Quản trị viên
    Cây B+ phải được ép vào trong khuôn khổ quy tắc của nó. Nó khác thường ở chỗ nào?

    - Nó khác thường ở chỗ không phải mỗi nút có thể cho phép chỉ một khoá. Mà số khoá trên mỗi nút phụ thuộc vào bậc của cây. Ví dụ người ta cho bậc của cây là b chẳng hạn, thì các nút con phải có tối thiểu b/2 khoá và có tối đa b khoá. Hay số lượng khoá của mỗi nút là m thì, m phải nằm trong khoảng [You must be registered and logged in to see this image.] . Khi số khoá mà nhỏ hơn b/2 thì đương nhiên phải gộp nút cho nó lớn hơn b/2. Và đương nhiên khi số khoá lớn hơn thì phải tách nút thành 2 nút con.
    - Nút gốc đặc biệt nên cho phép tối thiểu là 1 khoá.
    Bây giờ ta xem lại cái bảng sau nhé:
    Kiểu NodeKiểu conSố con tối thiểuSố con tối đa Ví dụ minh hoạ b = 7Ví dụ minh hoạ b = 100
    Nút gốcKeys1b1 - 71 - 100
    Nút gốc
    Nút trong hoặc nút lá
    2b2 - 72 - 100
    Nút trong
    Nút trong hoặc nút lá
    [You must be registered and logged in to see this image.]b4 - 750 - 100
    Nút lá
    Keys[You must be registered and logged in to see this image.]b - 13 - 650 - 99

    Với 1 cây bậc b và có chiều cao h:


    • Số lượng records tối đa có thể lưu được: nmax = bhbh − 1



    • Số lượng records tối thiểu có thể lưu được:[You must be registered and logged in to see this image.]



    • Số lượng khoá tối thiểu là: [You must be registered and logged in to see this image.]



    • Việc lưu trữ cây O(n)
    • Thao tác chèn 1 record O(log bn)
    • Thao tác tìm 1 record O(log bn)
    • Loại bỏ 1 record O(log bn)
    • Truy vấn với k phần tử trong giới hạn yêu cầu O(log bn + k)
    • Truy vấn phân trang với trang cỡ s và số trang p yêu cầu O(p * s)


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    6 Re: [Kinh nghiệm]Nói về B++ tree on Mon May 13, 2013 4:53 pm

    thienphitq


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Ban HaiYen đưa ra cái view quá tuyệt vời, chẳng cần đọc, chỉ cần nhìn cũng hiểu qua đường link bạn cung cấp [You must be registered and logged in to see this link.]

    7 cho đề sao hok cho lời giải on Wed May 15, 2013 4:18 pm

    thienthanh650


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Admin đã viết:Các đề tham khảo về câu dạng này:
    1. Hãy cho biết kết quả của các thao tác sau khi thực hiện tren cây B-Tree với bậc m=5(vẽ cây minh họa từng bước) khi lần lượt thêm các khóa sau vào cây: 15, 35, 26, 18, 22, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25, 11, 97, 48, 63, 78, 20.

    2. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 7, 67, 43, 45, 50, 99, 95, 70, 75, 55, 60, 8, 12, 5, 3, 20, 22, 15, 26, 65, 80,30, 40,19, 57, 89. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.

    3. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 13, 5, 8, 11, 65, 1, 45, 33, 87, 21, 4, 55, 20, 34, 39, 32, 90, 56, 43, 68, 59, 49, 23, 47, 14, 24. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.

    4. a. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 5, 34, 22, 1, 32, 6, 7, 23, 45, 56, 3, 89, 51, 59, 33, 50, 9, 46, 83, 11, 19, 65, 49, 43, 38, 17, 92, 27, 82. Trình bày tiến trình khi lần lược thêm từng khóa trên vào cây.
    b. Cho biết kết quả cuối cùng cua B+-tree lần lượt thêm các khóa ở câu a.

    5. a Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 20, 78, 63, 48, 97, 11, 25, 45, 24, 38, 32, 8, 27, 46, 13, 42, 22, 18, 26, 35, 15, 82, 92, 3, 51. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.
    b. Cho biết kết quả cuối cùng cua B+-tree (m=5) tuong ứng với cây B-Tree ở câu a.

    6. a.Cho cây B-Tree với bậc m=6. Lần lượt thêm các khóa sau vào cây: 57, 21, 34, 15, 58, 47, 94, 17, 46, 11, 49, 86, 82, 20, 99, 48, 95, 44, 55, 38, 63, 66, 59, 39, 78, 16, 68, 64, 90, 112, 135, 104 và 10. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.
    b.Cho biết kết quả cuối cùng cua B+-tree lần lược thêm các khóa ở câu a.

    7. a. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 56, -54, 84, 75, 48, 59, 83, -96, 67, -90, 85, 89, 90, 13, 9, 68, 25, 60, 5, 19, 52, 21, 28, 66, 45, 4, 50, 64, 24, 37, 47, -78, -76, 87, 2, 54, 81, 17, -42, 6, 74. Trình bày tiến trình khi lần lược thêm từng khóa trên vào cây.
    b. Trình bày tiến trình khi lần lược xóa khóa -42 và 25.

    Cho đề sao hok cho lời giải trời vậy cho đề làm gì hả

    8 Re: [Kinh nghiệm]Nói về B++ tree on Wed May 15, 2013 4:21 pm

    thienthanh650


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    Admin đã viết:Các tài liệu về B+ tree toàn bằng tiếng Anh (Kể cả của thầy và cả trên Internet, có google cũng không có bản tiếng Việt nào nên hồn) thôi thì gõ một ít ra đây để tiện trao đổi. Một số bạn có hỏi gì thì hỏi lên diễn đàn, đừng có bom vào thùng thư của tôi, mỗi ngày nhận tới vài trăm thư, nên tôi chỉ đọc những thư quan trọng thôi còn lại là AutoDelete, nên hết sức thông cảm.
    Tiện thể nhắc luôn mấy cái anh chàng và cô nàng không chịu đọc kỹ, mà đã nhắc lại nhiều lần rồi là đã ở nhóm "Học viên DS" thì đừng có đòi tham gia vào nhóm khác (Thành viên đọc được mọi thứ) vì có tham gia vào thì sẽ đảo bit = 0 sẽ bị cấm không đọc được đâu. Đã nhắc đi nhắc lại rồi mà vẫn cứ lao đầu xin chết thì cũng lạ đấy nhé.

    Thôi năm mới nói tý cho vui, gõ một ít về bài học cho những người lười học thì lên đây đọc. Mà nói thật là nếu cứ học kiểu này có khi phải thuê bạn Hải Yến ở trường Mầm Non Hoa Phượng Đỏ học hộ và thi hộ mất thôi.

    B+ Tree là một cấu trúc dữ liệu dạng cây ‘đa phân cân bằng’. Cấu trúc một node của nó thường được chia làm nhiều phần. Cây được tổ chức với một qui tắc nhất định được tạo ra từ đầu. Thường thì giá trị của các node tăng dần từ trái qua phải, node con bên trái sẽ chứa giá trị nhỏ hơn node con bên phải...

    [You must be registered and logged in to see this image.]

    B + Tree là một sự tổng quát hóa của cây nhị phân tìm kiếm (BST). Sự khác biệt chính giữa chúng là số lượng node con của B+Tree nó sẽ nhiều hơn chứ không bị giới hạn bởi hai phần tử như của cây nhị phân tìm kiếm. Mục tiêu ở đây là làm sao để giảm tối đa số lần truy xuất các thiết bị ngoại vi (ở đây là đĩa). Tại bất cứ thời điểm nào chúng ta sẽ thử định vị những bản ghi, chúng ta muốn độ cao của cây đa phân này phải là nhỏ nhất để giảm chi phí tìm kiếm, để đạt được mục tiêu này thì số lượng nhánh trong cây phải lớn.

    Nếu B+Tree có bậc là m thì môt node của nó sẽ có tối đa m nhánh con và có m-1 khóa để tìm kiếm.

    • Các record chỉ được lưu ở nút lá của cây

    • Tất cả các nút (ngoại trừ nút gốc) có tối thiểu là m/2 (ở đây phép chia nguyên làm tròn về phía trên, nếu lẻ) và tối đa là m nhánh con.

    • Nút gốc và lá phải ít nhất có 2 con.

    • Bên trong một node lưu giá trị tìm kiếm, một vài khóa được sử dụng như những “người chỉ đường” cho quá trình tìm kiếm. Những khóa này cần phải được sắp xếp theo môt thứ tự thống nhất trừ trước (tăng dần từ trái qua phải).

    • Tùy thuộc vào kích thước của một record so với kích thước của một khóa thì node lá của B+Tree bậc m có thể lưu nhiều hơn hoặc ít hơn m records. Thông thường kích thước của một node là bội số của một khối dữ liệu trong ổ đĩa (bên windows mặc định là 512byte).

    • Các node lá của cây thường được liên kết với nhau để tạo thành một danh sách liên kết, điều này nhằm mục tiêu là để không phải duyệt trở lại node gốc trong quá trình duyệt tìm kiếm.

    Ví dụ một cây B+Tree:
    [You must be registered and logged in to see this image.]
    xùy cái ví dụ cùi bắp hok bit lượm ở đâu nhìn dek có hiêu gì hết

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs