Эдвард Мак-Крейт¶
Эдвард Мак-Крейт (англ. Edward McCreight) — американский учёный в области информатики, известный как один из создателей алгоритма B-дерева (B-tree) и соавтор ранних версий операционной системы Unix. Работал в Xerox PARC, где внёс вклад в развитие вычислительной техники, в частности, в создание персонального компьютера Xerox Alto.
¶Биография
Эдвард Мак-Крейт родился в 1940 году в США. Получил степень бакалавра по математике в Принстонском университете, а затем степень доктора философии (PhD) по информатике в Стэнфордском университете. В Стэнфорде его научным руководителем был Дональд Кнут, один из пионеров компьютерных наук. Диссертация Мак-Крейта была посвящена алгоритмам поиска и сортировки данных.
После завершения обучения в 1969 году Мак-Крейт поступил на работу в исследовательский центр Xerox PARC (Palo Alto Research Center), где проработал до 1975 года. В PARC он занимался разработкой операционных систем и алгоритмов для новых вычислительных машин.
В 1975 году Мак-Крейт перешёл в компанию Apple Computer, где работал над программным обеспечением для персональных компьютеров. В 1980-х годах он основал собственную компанию по разработке программного обеспечения, а затем работал в различных технологических фирмах, включая Digital Equipment Corporation (DEC) и Hewlett-Packard.
¶Вклад в информатику
¶Создание B-дерева
Наиболее известным достижением Мак-Крейта является изобретение B-дерева (B-tree) — структуры данных для хранения и поиска информации на внешних носителях, таких как жёсткие диски. B-дерево было разработано в 1970 году совместно с Рудольфом Байером (Rudolf Bayer) в рамках работы над алгоритмами для системы управления базами данных.
Основная идея B-дерева заключается в том, что оно позволяет эффективно выполнять операции вставки, удаления и поиска данных, используя минимальное количество обращений к диску. Ключевая особенность — высокая степень ветвления (каждый узел может содержать множество ключей и дочерних узлов), что снижает глубину дерева и, следовательно, количество операций ввода-вывода.
B-деревья стали основой для большинства современных систем управления базами данных (СУБД), файловых систем (например, NTFS, ext4, HFS+) и других приложений, где требуется быстрый доступ к большим объёмам данных. Название «B-дерево» по одной из версий расшифровывается как «Bayer-tree» (по фамилии соавтора), по другой — как «balanced tree» (сбалансированное дерево) или «Boeing tree» (по названию компании Boeing, где работал Байер).
¶Работа над операционной системой Unix
В 1970-х годах Мак-Крейт участвовал в разработке ранних версий операционной системы Unix в Xerox PARC. Вместе с Кеном Томпсоном (Ken Thompson) и Деннисом Ритчи (Dennis Ritchie) он работал над реализацией системы ввода-вывода и файловой системы. В частности, Мак-Крейт написал драйверы для дискового накопителя и реализовал поддержку многозадачности.
Хотя его вклад в Unix не столь масштабен, как у Томпсона или Ритчи, он считается одним из первых разработчиков, адаптировавших Unix для работы на оборудовании Xerox.
¶Участие в создании Xerox Alto
В Xerox PARC Мак-Крейт также принимал участие в проекте по созданию персонального компьютера Xerox Alto (1973 год). Alto был первым компьютером с графическим интерфейсом пользователя (GUI), использующим мышь и оконную систему. Мак-Крейт занимался разработкой программного обеспечения для этого компьютера, включая редактор текста и систему управления файлами.
¶Признание и награды
За вклад в развитие информатики Эдвард Мак-Крейт был удостоен нескольких наград. В 2000 году он получил премию ACM SIGMOD Edgar F. Codd Innovations Award за создание B-дерева. В 2012 году вместе с Рудольфом Байером был награждён премией IEEE Computer Society Charles Babbage Award за фундаментальные достижения в области структур данных.
¶Основные публикации
- Bayer, R., McCreight, E. (1972). Organization and Maintenance of Large Ordered Indexes. Acta Informatica, 1(3), 173–189. — Статья, в которой впервые описана структура B-дерева.
- McCreight, E. (1977). A Space-Economical Suffix Tree Construction Algorithm. Journal of the ACM, 23(2), 262–272. — Работа по построению суффиксных деревьев, используемых в алгоритмах поиска подстрок.
¶Интересные факты
- Название «B-дерево» не имеет официальной расшифровки. В интервью Рудольф Байер упоминал, что буква «B» может означать «Bayer» (по его фамилии), «balanced» (сбалансированное) или «Boeing» (по названию компании, где он работал). Эдвард Мак-Крейт в одном из интервью предположил, что название было выбрано случайно.
- Мак-Крейт является одним из немногих учёных, кто работал одновременно в Xerox PARC, Apple и DEC — трёх ключевых компаниях, сформировавших современную компьютерную индустрию.
- В 2010 году Мак-Крейт дал интервью для проекта «Oral History of Computer Science» (Устная история информатики), где подробно рассказал о создании B-дерева и работе в PARC.
¶Источники
- Bayer, R., McCreight, E. (1972). Organization and Maintenance of Large Ordered Indexes. Acta Informatica, 1(3), 173–189.
- McCreight, E. (1977). A Space-Economical Suffix Tree Construction Algorithm. Journal of the ACM, 23(2), 262–272.
- Oral History of Edward McCreight. Computer History Museum, 2010.
- Knuth, D. (1998). The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley. — Раздел о B-деревьях.
- IEEE Computer Society Charles Babbage Award — 2012. IEEE Computer Society.